WikiDer > Fermat.-Prime-Test

Das Fermat-Prime-Test ist ein Wahrscheinlichkeitsrechnung Methode zum Testen, ob eine Zahl wahrscheinlich eine Primzahl ist.

Theorie

Der Test basiert auf der Der kleine Satz von Fermat, die lautet: Für a Primzahl${displaystyle p}$ und ${displaystyle 1leq a$ gilt:

${displaystyle a^{p}äquivalent a{pmod {p}}}$

Um zu testen, ob eine Zahl ${displaystyle p}$ ist prim, man wählt zufällig Zahlen ${displaystyle 1leq a$ und prüfen Sie, ob die oben Gleichwertigkeit gilt. Die Äquivalenz gilt für alle Primzahlen, also wenn sie nicht für einen bestimmten Wert von gilt ${Anzeigestil a}$, ist ${displaystyle p}$zusammengesetzt. Wenn es viele Werte von gibt ${Anzeigestil a}$ sind, für die die Äquivalenz Gut trifft zu, das kann man sagen ${displaystyle p}$ wahrscheinlich prim oder a Pseudoprime (eine zusammengesetzte Zahl, die Eigenschaften hat, die alle Primzahlen haben).

Schon seit ${Anzeigestil a}$ zufällig gewählt wird, kann es sein, dass für Nicht ein einziger gewählt ${Anzeigestil a}$ die Äquivalenz gilt nicht. Ist ${displaystyle n}$ eine zusammengesetzte Zahl, dann jedes ${Anzeigestil a}$ wofür:

${displaystyle a^{n-1}äquivalent 1{pmod {n}}}$

ein Fermat Lügner erwähnt. Wählen die Leute? ${Anzeigestil a}$ so dass:

${displaystyle a^{n-1}nicht gleich 1{pmod {n}},}$

dann wird ${Anzeigestil a}$ ein Fermat-Zeuge erwähnt aus der Tatsache, dass ${displaystyle n}$ zusammengesetzt ist.

Beispiel

Angenommen, wir wollen feststellen, ob nein = 221 ist prim. Wählen Sie ein beliebiges 1 ein < 221 von ein = 38. Äquivalenz oben prüfen:

${Displaystil a^{n-1}=38^{220}Äquiv. 1{pmod {221}}}$

Entweder ist 221 eine Primzahl oder 38 ist ein Fermat-Lügner; Deshalb haben wir uns für einen anderen entschieden ein ab 26:

${displaystyle a^{n-1}=26^{220}Äquiv. 169ot Äquiv. 1{pmod {221}}}$

221 ist also komponiert und 38 war tatsächlich ein Fermat-Lügner.

Algorithmus

Es Algorithmus kann in Pseudocode wie folgt erstellt werden:

Eingang: n > 1, von denen geprüft werden muss, ob sie prim ist oder nicht; k, eine ganze Zahl, die die Genauigkeit des Tests bestimmtExport: zusammengesetzt wenn nein ist zusammengesetzt, ist anders möglicherweise Ahle. wiederholen k mal: nimm was ein aus (1, nein−1] als gcd(ein,nein) ${displaystyle eq }$ 1, dann Ausgabe zusammengesetzt   wenn einnein−1${Anzeigestil oder Äquivalent}$1 (mod nein), dann Ausgabe zusammengesetztAusgabe möglicherweise Ahle.

Lücken im Test

Der Pannentest von Fermat ist nicht narrensicher. Ein wichtiges Problem für den Test ist eine besondere Art von zusammengesetzten Zahlen, die Carmichael-Zahlen. Das sind die zusammengesetzten Zahlen c mit der Eigenschaft, dass c eine Pseudoprimzahl (ein^c−1 ≡ 1 (mod c) ) ist für jeden ein mit gcd(ein,c) = 1. Auch jede Multiplikation von c ist selbst eine Pseudoprimzahl. Es gibt unendlich viele ursprüngliche Carmichael-Zahlen.^[1]

Richtigkeit

Wann nein eine zusammengesetzte Zahl ist, die keine Carmichael-Zahl ist, dann mindestens die Hälfte aller

${displaystyle ain (mathbb {Z} /nmathbb {Z} )^{*}}$

Zeugen von Fermat. Dies kann wie folgt bewiesen werden: let {ein₁, ein₂, ..., ein_ich} die Fermat-Lügner sind und ein ein Fermat-Zeuge. Dann gilt für ich = 1,2,...,ich Welche:

${displaystyle (acdot a_{i})^{n-1}=a^{n-1}cdot a_{i}^{n-1}äquivalent a^{n-1}cdot 1äquivalent a^{n-1 }nicht gleich 1{pmod {n}}.}$

Also jeder ein_ich gibt eine Zahl an ein·ein_ich, die auch ein Fermat-Zeuge ist, dh jeder Fermat-Lügner gibt einen Fermat-Zeugen ab, und daher ist die Anzahl der Fermat-Zeugen größer oder gleich der Anzahl der Fermat-Lügner. Daraus folgt, wenn nein zusammengesetzt und keine Carmichael-Zahl ist, dann mindestens die Hälfte aller ein Zeugen von Fermat.

Externer Link

• Pseudoprimzahlen bis 4999

Verweise