Primzahlen durch testen finden.

Große (mehrere hundert Stellen) Primzahlen lassen sich bislang 'effektiv' nur durch testen finden. Hier werden der Fermat Test und der Miller Rabin Test vorgestellt.

Fermat Test

Satz von Euler: a φ(n) ≡ 1 mod n
Für alle Primzahlen p gilt: φ(p) = p - 1. So ergibt sich der kleine Satz des Fermat.
Für alle natürlichen Zahlen p, a mit 1 < a < p gilt, falls p eine Primzahl ist,
ap-1 mod p = 1.
Schauen wir mal für 7: 26 mod 7 = 64 mod 7 = 1. Bingo! Wird das ein Primzahltest?

  • Teste p
  • Wähle a mit 1 < a < p
  • Ist ggT(p, a) = 1, dann weiter, sonst zusammengesetzte Zahl, Ende
  • Ist ap-1 mod p = 1, dann Test bestanden, sonst zusammengesetzte Zahl
  • Ende

Leider nicht. Wie sieht es mit 561 aus? Der Test wird für alle a mit ggT(561, a) = 1 bestanden. 561 ist aber zusammengesetzt aus 3 * 11 *17. Testet man also in diesem Fall nicht mit einer der drei Zahlen oder deren Vielfachen, wird der Test bestanden. Wer kann das vorher wissen? In dem Fall könnte man ja auf den Test verzichten.
Das Programm FermatPrime testet nach dem oben beschriebenem Verfahren die ungeraden Zahlen von 501 - 601 und 75361 zur Basis 2. 561 und 75361 bestehen den Test. Man kann mal andere Basen und Bereiche testen und wird finden, daß es Zahlen gibt, die den Test mit anderen Basen bestehen. Noch schlimmer: Es gibt zusammengesetzte Zahlen, die für alle ihnen teilerfremde Basen den Test bestehen. Sie werden Carmichael Zahlen genannt. Seit 1994 weiß man, dass es unendlich viele gibt.
Der Test ist also ungeeignet, um Primzahlen zu finden. Alle Basen zu testen scheidet bei großen Zahlen aus. Es muß was anderes her.

Quelltext ein-/ausblenden

Miller Rabin Test

Dieser Primzahltest ist nach Garry Miller und Michael O. Rabin benannt. Er liefert Aussagen von der Sorte: "Die getestete Zahl ist mit der Wahrscheinlichkeit 1 - ½ Anzahl Tests eine Primzahl." D.h. nach 10 - 50 Tests sollte es mit dem Teufel zugehen, daß man doch eine zusammengesetzte Zahl in der Hand hält. Aber: Es ist möglich! Leider muß man damit leben. Es ist praktisch (in angemessener Zeit) nicht möglich eine z.B. 500 stellige Zahl sicher einzuordnen, der dafür notwendige Aufwand ist zum Heulen.

Kern vom Miller - Rabin bleibt der kleine Satz von Fermat. Wir suchen jetzt einen Belastungszeugen gegen die prim Eigenschaft. Dazu werden drei Maßnamen getroffen:

  1. Der Exponent wird nicht mehr als p - 1 berechnet. Solange er gerade ist, wird er durch 2 geteilt. (Exponent halbieren ⇒ Wurzel ziehen, Exponent verdoppeln ⇒ Quadrieren)
  2. In einer Schleife werden im kleinen Fermat nacheinander mehrere zufällige Basen mit dem neuen Exponenten verwendet. Falls das Ergebnis X nicht die übliche 1, -1 bzw; p - 1 ist, testen wir den Belastungszeugen.
  3. Ein X gilt als Belastungszeuge, wenn x2 mod n = 1 und X ≠ 1 und X ≠ -1 bzw. X ≠ n-1. X wird ggf. so oft mit 2 potenziert wie der Exponent in Schritt 1 halbiert wurde.

Was soll die dritte Aktion? Wenn p eine Primzahl ist, dann ist Zp ein Körper, in dem nur zwei Lösungen für Quadratische Gleichungen existieren. Findet man ein X mit einer dritten Lösung, so ist Zp kein Körper und p kann keine Primzahl sein. X wird dann nicht trivale Wurzel von 1 mod p genannt.

Quelltext ein-/ausblenden