Pierre de Fermat formulierte 1640 (sinngemäß) den Satz:
Sei p eine Primzahl und die natürliche Zahl a kein Vielfaches von p, dann ist ap-1-1 durch p teilbar.
Für einen Primalitätstest eignet sich dieser Satz nicht, da seine Umkehrung nicht gilt. So ist zum Beispiel 2341-1-1 durch 341 teilbar, obwohl 341=11·31 keine Primzahl ist. Eine Zahl, die den genannten Satz von Fermat für eine geeignete Basis a belegt, heißt ‚Pseudo-Primzahl zu Basis a‘. So ist 3341-1-1 nicht durch 341 teilbar und man sagt 341 besteht den Fermat-Test zur Basis 3 nicht, wird also als zusammengesetzte Zahl identifiziert.
Aber es gibt (ganz selten) Zahlen, welche den Fermat-Test zu jeder Basis bestehen und trotzdem keine Primzahlen sind. Eine solche Zahl heißt ‚Carmichael-Zahl‘. Die Carmichael-Zahlen zwischen 1 und 100000 sind:
561, 1105, 1729, 2456, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361.
Man muss also weitere Tests durchführen, um zu verhindern, dass eine Carmichael-Zahl fälschlich als Primzahl identifiziert wird. Eine Hypothese zu einem solchen Test ist folgende:
F(n) bezeichne die n-te Fibonaccizahl. Wenn p≠5 Primzahl ist, dann gilt: mod(F(p – 1, p) + mod(F (p + 1), p) = 1.
Daraus folgt die Hypothese:
Wenn mod(F(p – 1, p) + mod(F (p + 1), p) ≠ 1, dann ist p≠5 keine Primzahl.
Diese Hypothese entlarvt – wenn sie zutrifft – vermeintliche Primzahlen als zusammengesetzt. Die Anwendung dieses Tests auf die ersten n Carmichael-Zahlen ergibt folgendes:
Anzahl n der ersten
n Carmichael- Zahlen
| Anzahl der darunter als
zusammengesetzt entlarvten
| Entlarvte in %
|
20
| 20
| 100
|
40
| 37
| 92,5
|
60
| 51
| 85
|
80
| 66
| 82,5
|
100
| 80
| 80
|
Selbst wenn die Hypothese bewiesen werden kann und wirklich alle zusammengesetzten Zahlen entlarvt, bleibt ein darauf gegründeter Test aus zwei Gründen unbefriedigend
- Die Rechenzeiten sind hoch.
- Seine Wirkung lässt mit steigender Zahlengröße nach.
Aber das Nachlassen seiner Wirkung ist zum Glück nicht proportional zur Größe der getesteten Zahl, sodass auch für sehr große Carmichael-Zahlen noch eine gewisse Wirkung dieses Tests erwartet werden darf.
