Nero Wolfe

Der kleine Fermat-Satz von Pierre de Fermat entdeckt, macht eine Aussage über die Eigenschaften von Primzahlen:

Wenn eine natürliche Zahl n eine Primzahl ist, dann gilt

$2^{n}\equiv 2\mod n$ ist.

Hätte man diese Aussage umdrehen können, also sagen können, das wenn für eine natürliche Zahl n gilt:

$2^{n}\equiv 2\mod n$

diese eine Primzahl ist, hätte man einen prima Primzahlengenerator bekommen können. Dem ist aber nicht so.

Man kann aber den Satz auf alle Basen 1 < b < n erweitern. Wenn man also sagen kann, das bei einem natürlichen n für alle Basen b mit 1 < b < n gilt:

$b^{n}\equiv b\mod n$

dann muß diese Zahl n eine Primzahl sein.

Dazu muß man nicht alle Basen 1 < b < n durchtesten, sondern es reicht, das man aller Primzahlen p 1 < p < n benutzt.

Der Nachteil an diesem verfahren ist, das es sehr Langsam und aufwendig ist (das Testen auf Primzahlen über die Teilbarkeit ist schneller).

Wie funktioniert der Fermatsche Satz? Wenn main eine Zahl immer wieder mit sich multipliziert, dann bekommt man gewisse Zyklen bezüglich der Modulo-Operation:

Beispiel: 7

	2	2 mod 7	3	3 mod 7	5	5 mod 7
0	1	1	1	1	1	1
1	2	2	3	3	5	5
2	4	4	9	2	25	4
3	8	1	6	6	20	6
4	2	2	18	4	30	2
5	4	4	12	5	10	3
6	8	1	15	1	15	1
7	2	2	3	3	5	5

und so weiter. In Bezug auf die 7 ergibt sich bei der 2 folgender Zyklus: .. 1, 2, 4, 1, 2, 4, .. . Bei der 3: .. 1, 3 ,2 ,6, 4, 5, 1, 3, .. .

Für alle drei Basen 2, 3 und 5 gilt zur Zahl 7 folgende Regel:

$a^{(c*n)-n}\equiv a\mod n$

Im Beispiel des 2er-Zyklus .. 1, 2, 4, 1, 2, 4, .. zeigt sich, daß man den Algorithmus verkürzen kann, wenn sich zeigen läßt, daß der Zyklus kürzer .. 1, 2, 4, .. ist, als benötigt.

Ausserdem hat es sich als Sinnvoll gezeigt, daß man folgende Formel benutzt:

$a^{n-1}-1\equiv 0\mod n$

Mit dem Fermatschen Primzahltest - entwickelt von dem "Freizeitmathematiker" Pierre de Fermat - kann man aussagen, ob eine Zahl mit hoher Wahrscheinlichkeit eine Primzahl ist. Daher wird dieses Verfahren auch PRP-Test (= probable prime) genannt.

Anwendung des Kleinen Fermatschen Satzes

Direkt aus dem Kleinen Fermatschen Satz folgt:

Ist p eine Primzahl, dann ist n^p-1 -1 durch p teilbar für alle natürlichen Zahlen n < p.

Dies kann man mit Hilfe der Modulo-Funktion schreiben als:

Für alle Primzahlen p gilt (n^p-1 -1)mod p = 0 mit n < p.

oder auch:

Für alle Primzahlen p gilt (n^p-1)mod p = 1 mit n < p.

Beispiel: p = 5 ist eine Primzahl

         n=1:  15-1 -1 =   0  ist teilbar durch 5
         n=2:  25-1 -1 =  15  ist teilbar durch 5
         n=3:  35-1 -1 =  80  ist teilbar durch 5
         n=4:  45-1 -1 = 255  ist teilbar durch 5

Carmichael-Zahlen

Es gibt allerdings auch Zahlen q, die keine Primzahlen sind und für dennoch gilt:

n^q-1 -1 durch q teilbar für alle natürlichen Zahlen n < q, bei denen n kein Teiler von q ist.
Solche Zahlen heißen Carmichael-Zahlen.

Diese Zahlen sind benannt nach dem amerikanischen Mathematiker Robert Daniel Carmichael (1879 - 1967).

Zwar gibt es unendlich viele Carmichael-Zahlen (das ist seit 1992 bekannt), aber im Vergleich zur Anzahl der Primzahlen sind es sehr wenige. Unter 100.000 gibt es nur die folgenden 16 Carmichael-Zahlen: 561 (=3·11·17), 1105, 1729 (=7·13·19), 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, and 75361.

Weitere Eigenschaften von Carmichael-Zahlen:

• Jede Carmichael-Zahl hat mindestens 3 Primfaktoren.
• Unter den Teilern einer Carmichael-Zahl ist keine Quadratzahl.
• Sei n eine Carmichael-Zahl, p ein Primteiler von n. Dann ist (n-1) durch (p-1) teilbar.
• Sei p > 3 eine Primzahl derart, dass auch 2p-1 und 3p-2 Primzahlen sind, dann ist n = p(2p-1)(3p-2) eine Carmichael-Zahl. Beispiel: p=7 --> n=7·13·19=1729.

Aus dem obigen Satz folgt sofort die folgende Aussage:

Findet man eine natürliche Zahl n < p mit der Eigenschaft n^p-1 -1 ist nicht durch p teilbar, dann ist p keine Primzahl.

Beispiel: p = 21 ist keine Primzahl, denn für n = 2 gilt

221-1mod 21 = 220mod 21 = ((210mod 21)2)mod 21 = 4 ungleich 1, d.h. p = 21 ist keine Primzahl.
Sollte man diesen Test für die Basis 13 machen, denn für 13,
und in diesem Fall nur für die 13 ist 21 pseudoprim.

Fermatscher Primzahltest

Leider kann man mit den Regeln der Aussagenlogik nicht die Umkehrung herleiten, aber es gilt die folgende Regel, der so genannte Fermatsche Primzahltest:

Wenn n^p-1 -1 durch p teilbar für alle natürlichen Zahlen n < p, dann ist p mit hoher Wahrscheinlichkeit eine Primzahl.

Der Test weist nämlich fälschlicherweise auch jede Carmichael-Zahl als Primzahl aus. Da diese jedoch - wie oben beschrieben - sehr selten auftreten, ist die Fehlerwahrscheinlichkeit des Primzahltests gering.
Eine absolute Sicherheit wird allerdings durch die Carmichael-Zahlen verhindert.

Pseudo-Primzahlen

Man kann nun versuchen, diesen Test zu vereinfachen und den Rechenaufwand deutlich zu reduzieren, wenn man eine etwas geringere Wahrscheinlichkeit in der Primzahlaussage in Kauf nimmt.

Dazu folgende Definition:

Eine natürliche Zahl p heißt Pseudo-Primzahl zur Basis a bzw. pseudoprim zur Basis a, wenn a^p-1 -1 durch p teilbar und die natürliche Zahl a < p ist.

• Findet man eine Zahl a < p, zu deren Basis p nicht pseudoprim ist, dann ist p keine Primzahl, was direkt aus dem Kleinen Fermatschen Satz folgt.
• Ist p zu jeder Basis a < p pseudoprim, dann ist p entweder eine Primzahl oder eine Carmichael-Zahl.
• Ist p pseudoprim zur Basis a, dann könnte p eine Primzahl sein. Man sagt auch, die Zahl a sei ein Zeuge dafür, dass p eine Primzahl ist. Findet man weitere Zahlen zu deren Basis p pseudoprim ist, dann hat man weitere Zeugen dafür, dass p eine Primzahl ist. D.h. die Wahrscheinlichkeit steigt, dass p eine Primzahl ist.

Es gibt relativ wenig Zahlen p, die nicht prim sind aber dennoch pseudoprim zu einer Basis a.

Beispiele: p = 341 = 31·11 ist pseudoprim zur Basis 2, denn 2^341-1 -1 ist teilbar durch 341. (Dieses Beispiel entdeckte P.F.Sarrus im Jahr 1819.) Der Nachweis ist mit Methoden der Restklassen vergleichsweise einfach. In dem Artikel Restklassen wird dieser Nachweis als Anwendungsbeispiel demonstriert.

Ach ja, 341 ist pseudoprim zu den Primbasen 2, 23, 29, 47, 61, 89, 97, 101, 109, 139, 151, 157, 163, 233, 263, 271, 277, 281, 283, 311 und 337.

Auch p = 91 = 7·13 ist pseudoprim zur Basis 3, denn 3^91-1 -1 ist teilbar durch 91.

C.Pomerance, J.L.Selfridge und S.S.Wagstaff Jr. zeigten im Jahre 1980, dass es unterhalb von 25.000.000.000 zwar 1.091.987.405 Primzahlen, aber nur 21.853 Pseudo-Primzahlen zur Basis 2 gibt.

Daraus folgt:

Ist p pseudoprim zur Basis 2, dann ist p mit hoher Wahrscheinlichkeit eine Primzahl.

Für die Praxis bedeutet das: Oft reicht der Nachweis aus, dass p pseudoprim ist zur Basis 2. Will man die Sicherheit weiter erhöhen, dann muss man eben weitere Zeugen finden, d.h. weitere Zahlen a, zu deren Basis p pseudoprim ist.
Im Grenzfall testet man alle Zahlen a < p, d.h. man führt den gesamten Fermattest durch.

Verbesserungen des Fermatschen Primzahltests

Gary Miller und Michael O.Rabin verbesserten den Fermattest im so genannten Rabin-Miller-Test. Nicht-Primzahlen erkennt er mit doppelter Wahrscheinlichkeit.

Im Jahre 1980 stellten die Mathematiker Leonard M. Adleman, R.S. Rumely, H. Cohen und H.W. Lenstra Jr den nach ihnen benannten ARCL-Test vor. Dieser ist eine Weiterentwicklung des Fermatschen Primzahltests, indem er Carmichael-Zahlen erkennt.

Literatur

• C.Pomerance,J.L.Selfridge, S.S.Wagstaff Jr., "The pseudoprimes to 25 · 109," Math. Comp., 35:151 (1980) 1003-1026.
• Paolo Ribenboim, The new Book of Prime Number Records, (1996) Springer Verlag