r-facher Fermattest

13.09.2020, 22:15	Julia 004	Auf diesen Beitrag antworten »
r-facher Fermattest Meine Frage: Was ist der r-fache Fermattest? Meine Ideen: Der r-fache Fermattest dient doch der Vorhersage mit Wahrscheinlichkeit 1-2^k, ob es sich um eine Nicht-Carmichael Zahl handelt, oder?
14.09.2020, 10:27	HAL 9000	Auf diesen Beitrag antworten »
Wahrscheinlichkeit $\begin{eqnarray} 1-2^k \end{eqnarray}$ ??? Abgesehen davon, dass hier von keinem $\begin{eqnarray} k \end{eqnarray}$ die Rede ist, macht diese Formel für alle $\begin{eqnarray} k\geq 1 \end{eqnarray}$ keinerlei Sinn hinsichtlich eines Wahrscheinlichkeitswerts. Wie auch immer: $\begin{eqnarray} r \end{eqnarray}$ -fach heißt einfach nur, dass man den Fermattest statt für einen Wert $\begin{eqnarray} a \end{eqnarray}$ für $\begin{eqnarray} r \end{eqnarray}$ zufällig gewählte Werte mit $\begin{eqnarray} 1<a<N \end{eqnarray}$ durchführt. Das Korollar besagt nun, dass im Fall $\begin{eqnarray} a^{N-1}\equiv 1\bmod N \end{eqnarray}$ für all diese $\begin{eqnarray} r \end{eqnarray}$ Werte man mit Mindestwahrscheinlichkeit $\begin{eqnarray} 1-2^{-r} \end{eqnarray}$ davon ausgehen kann, dass $\begin{eqnarray} N \end{eqnarray}$ eine Primzahl oder aber eine Carmichael-Zahl ist.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »