Primzahltest durch Probedivision
Das Verfahren beruht auf der Tatsache, daß eine natürliche Zahl n 1, die außer 1 keinen Teiler d n1/2 besitzt, prim ist; ist nämlich n = d1d2 mit d1,d2 N, so ist d1 n1/2 oder d2 n1/2. Um festzustellen, ob eine Zahl n Primzahl ist, braucht man nur für alle Primzahlen p n1/2 zu testen, ob sie n teilen.
Der Aufwand für diesen Primzahltest wird gegeben durch die Anzahl.
(n1/2) := #{p n1/2 | p prim}
der Probedivisionen, die notwendig sind für den Beweis, daß n eine Primzahl ist. Beachtet man die bekannten Abschätzungen von J. Rosser und L. Schoenfeld
für x > 17 ist (x) > x/log x
und für x > 1 ist (x) < 1.25506(x/log x)
und betrachtet man beispielsweise eine Zahl n größer als 10100, müßte man mehr als 1050/log 1050 > 0.86·1048 Probedivisionen durchführen, um die Primheit von n zu beweisen: eine undurchführbare Aufgabe! (log x bezeichnet den natürlichen Logarithmus von x.)
Die Probedivision ist ein exakter (oder terministischer) Primzahltest, d.h. ein Verfahren, das beweist, daß eine Zahl n prim ist.
Daneben gibt es eine Anzahl von Verfahren, die feststellen können, daß eine Zahl n mit hoher Wahrscheinlichkeit prim ist. Solche Verfahren nennt man probabilistische Primzahltests. Ein derartiger Test ist der
Fermat Test.
(Er beruht auf dem sogenannten
,,Kleinen Satz von Fermat". Ist n eine Primzahl, so gilt für alle zu n teilerfremden Zahlen a
an-1 1 mod n
iMit diesem Satz läßt sich feststellen, ob eine Zahl n zusammengesetzt ist. Man wählt eine Zahl a, (1 < a < n), und berechnet an-1 mod n. Ist dies1, so ist n zusammengesetzt. Ist umgekehrt an-1 mod n = 1, so folgt hieraus nicht, daß n prim ist. Hat man aber für viele n keinen Beweis für die Nicht-Primheit von n gefunden, so wird man folgern, daß n wahrscheinlich prim ist.
Wir nennen eine zusammengesetzte Zahl n eine Pseudoprimzahl zur Basis a, falls
an-1 1 mod n
gilt. Ist n eine Pseudoprimzahl zur Basis a für allea, die teilerfremd zu n sind, dann heißt nCarmichael-Zahl. Es gibt unendlich viele Carmichael-Zahlen. (Ein Beispiel für eine Carmichael-Zahl ist n = 561.) Aus diesem Grund ist der Fermat-Test für die Praxis nicht geeignet.
Anders verhält es sich bei den folgenden Tests.
Miller Test.
Grundlage hierfür ist die folgende Verschärfung des kleinen Satzes von Fermat.
Satz (Miller). Schreiben wir eine ungerade ganze Zahln > 1 in der Formn-1 = 2eu mit ungeradem u, so sind die folgenden Aussagen äquivalent
(i)
n ist prim.
(ii)
Für alle zu n teilerfremden Zahlen a gilt entweder
(1)
au 1 mod n
oder es gibt ein k in der Menge {0,1,...,e-1} mit
(2)
a2ku -1 mod n
der Test ist deterministisch, er kann nach hinreichend vielen Versuchen für jede natürliche Zahl entscheiden, ob sie prim oder zusammengesetzt ist. Wie die Probedivision ist er aber für große Zahlen zu aufwendig. Er läßt sich jedoch zu einem schnellen probabilistischen Test modifizieren, dem
Miller-Rabin-Test
Ist n eine zusammengesetzte Zahl und findet man ein zu n teilerfremdes a, für das weder (1) noch (2) für ein k mit 0 k e-1 gilt, so ist a nicht prim. Eine solche Zahl nennt man nach Rabin einen Zeugen gegen die Primheit von n. Eine Abschätzung der Anzahl dieser Zeugen geht auf Rabin zurück, und eine einfache Version seines Resultates ist enthalten in folgendem
Satz (Rabin). Sei n > 3 eine ungerade zusammengesetzte Zahl, Dann ist die Anzahl dera n-1, die zu n teilerfremd und keine Zeugen gegen die Primheit von n sind, höchstens (n-1)/4.
Zur Anwendung des Miller-Rabin-Tests auf eine ungerade Zahl n wählt man eine beliebige Zahl a mit 2 a n-1. Ist der ggT(a,n) > 1, so ist n zusammengesetzt. In anderen Fall berechnet man au,a2u,...,a2e-1u. Ist a ein Zeuge gegen die Primheit von n, so ist gezeigt, daß n nicht prim ist. Nehmen wir an, daß a kein Zeuge gegen die Primheit von n ist. Dann ist die Wahrscheinlichkeit dafür, daß n zusammengesetzt ist, höchtens 1/4. Wiederholt man den Miller-Rabin-Test t-mal, so ist n mit einer Wahrscheinlichkeit > 1-(1/4)t eine Primzahl.
Wir haben den Miller-Rabin-Test implementiert. Er benötigt für einen Test bei einer Zahl n den Größe 10100 ca. 0,062 Sekunden (bei 1010000 ca. 3526 Sekunden) auf einem Super-SPARC-Prozessor mit 40MHz.
Literatur
- 1.] K.-H. Indlekofer, A. Járai, Largest known twin primes, Math. Comp. 65(1996), 427-428. MR 96d:11009
- [2.] K.-H. Indlekofer, A. Járai, Some world records in computational number theory, Leaflets in Mathematics, Janus Pannonius University, Pécs, 6(1998), 49-56, ISSN 1416-0935
- [3.] K.-H. Indlekofer, A. Járai, Largest known twin primes and Sophie Germain primes, Math. Comp. 68(1999), 1317-1324. MR 99k:11013