Hintergrundwissen
Der MILLER-RABIN Primzahltest
Der MILLER-RABIN Primzahltest ist ein probabilistischer Primzahltest, der auch bei grossen Zahlen schnell und mit beliebig hoher Wahrscheinlichkeit Primzahlen erkennt.
Der MILLER-RABIN Primzahltest prüft mit einer zufälligen Basis, ob die Eigenschaft der starken Pseudoprimzahl erfüllt ist. Falls nicht, ist die Zahl keine Primzahl. Falls ja, ist sie entweder eine Primzahl oder eine starke Pseudoprimzahl zur zufälligen Basis.
Sei n eine natürliche Zahle und A:={a| n starke Pseudoprimzahlen zur Basis a}. Nach einem Satz von MILLER-RABIN kann die Menge der starken Pseudoprimzahlen abgeschätzt werden duch
#A <= 1/4 φ(n)
Damit ist die Wahrscheinlichkeit, das n eine starke Pseudoprimzahl ist, wenn man die Basis zufällig auswählt:
#A / φ(n) <= 1/4
Um die Fehlerwahrscheinlichkeit (n ist starke Pseudoprimzahl) zu minimieren, kann man den Test wiederholen. Bei k Wiederholungen sinkt die Fehlerwahrscheinlichkeit auf höchstens (1/4)k.
Der Code
INPUT: ungerade Zahl n;
a = RANDOM(2,n-1);
t=n-1;alpha=0; WHILE t mod 2 = 0 DO t=t/2; alpha=alpha+1; END
p=atmod n; pseudoprim=false; alpha=alpha-1;
if (p=n-1) OR (p=1) THEN pseudoprim=true;
WHILE (not pseudoprim) AND (alpha>0) AND (p>1) DO
p = p * p mod n;
alpha = alpha - 1;
if (p=n-1) THEN pseudoprim=true;
END
if pseudoprim THEN WRITE 'pseudoprim'; ELSE WRITE 'zerlegbar';
Siehe auch: mathworld