Verfahren zur Primzahluntersuchung
Diese Seite listet die wichtigsten Methoden zur Primzahlsuche und viele verschiedene Arten von Beweisen auf, die zur schnellen Primzahlbestimmung benutzt werden.- Prüfverfahren für kleine Primzahlen
- Grundlegende Sätze zur schnellen Primzahlbestimmung
- Klassische Tests
Prüfverfahren für kleine Primzahlen
Die drei folgenden Verfahren sind f¸r kleinen Primzahlprüfungen zwar noch ausreichend schnell, doch die Zeit, die ein Computer f¸r die Prüfung ben–tigt, steigt proportional zu der Anzahl der Stellen der Primzahlen an.
Sieb des Eratostenes (240 v.Chr.):Eine Liste aller Zahlen wird angelegt, in der alle Vielfachen der Primzahlen nacheinander ausgestrichen werden.
Normale Division:
Normale Teilung von n durch die Primzahlen bis zur Wurzel aus n.
Wheel factorization:
Beim der wheel factorization wird eine Liste angelegt, aus der zuerst alle Zahlen, die sich durch 2, 3 und 5 teilen lassen, herausgestrichen werden. Dann werden die verbleibenden Zahlen durch die kleiste, nicht ausgestrichene Zahl, in diesem Fall die 7, geteilt und so wird das bis zur Wurzel aus n weitergeführt. Läşt sich n dann immer noch nicht teilen, ist es eine Primzahl.
Grundlegende Sätze zur schnellen Primzahlbestimmung
Fermat's kleiner Satz:p ist eine Primzahl; a ist eine beliebige Ganzzahl.
Dann ist
In vielen F”llen, wenn p kein Teiler von a ist,
dann ergibt
Mit Fermat's kleinem Satz kann man sehr schnell beweisen, daş eine bestimmte Zahl keine Primzahl ist (wenn die Bedingung nicht zutrifft). Zu beweisen, daş eine Zahl eine Primzahl ist, wenn sie die Prüfung besteht, ist nicht m–glich, da dieser Satz noch nicht in seiner Umkehrung bewiesen werden konnte.
Probable-Primality (Mögliche Primzahlen):
Die zu überprüfende Primzahl n > 1; eine beliebige Ganzzahl a > 1.
Wenn
Dieser schnell auszurechnende Satz ist von Fermat's kleinem Satz ¸bernommen und l”şt sich auch genauso schnell berechnen. Der einzige Nachteil liegt darin, daß auch hier nur bewiesen werden kann, daß eine Zahl keine Primzahl ist.
Beispiele:
| 5 | 24 mod 5 = 1 | 34 mod 5 = 1 | 44 mod 5 = 1 |
| 7 | 26 mod 7 = 1 | 36 mod 7 = 1 | 46 mod 6 = 1 |
| 9 | 28 mod 9 = 4 | 38 mod 9 = 0 | 48 mod 8 = 7 |
| 11 | 210 mod 11 = 1 | 310 mod 11 = 1 | 410 mod 11 = 1 |
| 15 | 214 mod 15 = 4 | 314 mod 15 = 9 | 414 mod 15 = 1 Falsche Annahme |
| 21 | 220 mod 21 = 4 | 320 mod 21 = 9 | 420 mod 21 = 16 |
Klassische Tests und Ableitungen von den beiden oben genannten Sätzen
Proth's Satz:Wenn es nun eine Ganzzahl a gibt, bei der
Pepin's Test:
F(n) ist die n-te Fermatsche Zahl (F(n) = 2 2 n +1) mit
F(n) ist nur dann eine Primzahl, wenn
Pocklington's Satz (1914):
Angenommen, n-1 = q k R, wobei q eine Primzahl ist und kein Teiler von R ist.
Gibt es nun eine Ganzzahl a, bei der
a n-1 = 1 (mod n) unddann hat jeder Primfaktor q von n die Form q kR+1.
bei der der ggT von(a (n-1)/q-1) und n gleich 1 ist (teilerfremd),
Ein weiterer sehr bekannter Satz:
Angenommen,
Wenn es nun eine Ganzzahl a gibt, bei der
dann ist n eine Primzahl.a (n-1) = 1 (mod n) und
der ggT von (a (n-1)/q-1) und n gleich 1 ist,
Lucas-Lehmer Test (1930):
Der Lucas-Lehmer Test ist eine der schnellsten Primzahlpr¸fungen, die es heute gibt. Er wird für die Prüfung von Mersenne-Exponenten, das sind Primzahlen der Form 2 n-1 verwendet. Die rasante Geschwindigkeit dieses Tests wird dadurch unterstrichen, daß alle heutigen Primzahlrekorde dieser Form sind.
Zuerst legt man eine Tabelle mit den Variablen schritt, u und u2-2 an.
schritt = 0 und u = 4.
Nun berechnet man
In diesem Beispiel ist n = 5. (25-1 = 31)
| schritt | u | u2-2 mod 2n-1 |
|---|---|---|
| 0 | 4 | 14 mod 31 = 14 |
| 1 | 14 | 194 mod 31 = 8 |
| 2 | 8 | 62 mod 31 = 0 |
| 3 | 0 |
M(n) ist genau dann eine Primzahl, wenn im schritt(n-2)
Lucas-Lehmer-Test direkt testen
Top