Miller-Rabin

[Meisterschmied]

Abend an alle!

Mal eine Frage:

Bei der Zahl 29 bekomme ich mit dem Miller-Rabin-Verfahren heraus, dass die 29 zusammengesetzt ist.

Denn für die Basis = 2 gilt

2^7 mod 29 <> 1 und 2^7 mod 29 <> -1 bzw n-1;

(7 = (29-1) div 2^2)

Ist dies der Fall, muss 29 zusammengesetzt sein. Das ist natürlich Blödsinn, aber wo liegt mein Denkfehler?

Danke,

Meisterschmied

[negaH]

a^p mod p = a mod p ist Fermats kleiner Satz, abgeleitet ergibt sich a^(p -1) mod p == -1,+1 mod p. Eine strengere version dieses Testet ist p -1 = d*2^s, d ungerade dann muß a^d mod p = 1 mod p und a^(d * 2^r) mod p = -1 mod p sein für alle r's kleiner s. Dies ist der Strenge Pseudoprimzahltest. Dieser wird im Rabin Miller Verfahren zu zufälligen a benutzt.

In deinem Falle 2^26 mod 27.

http://www.utm.edu/research/primes/prove/prove2_2.html
http://primes.utm.edu/glossary/page....rt=MillersTest
http://primes.utm.edu/glossary/page.php?sort=StrongPRP

Gruß Hagen

[Meisterschmied]

Tag Hagen,

ich glaube, ich hab einen Fehler in meinem Algorithmus ausgemerzt, hab aber immer noch Probleme bei größeren Zahlen, zum Beispiel:
82321
Diese Zahl ist eine Primzahl. Ich bekomme als Zeugen aber a=2 und erhalte mit Hilfe der binären schnellen Exponention die Ergebnisse:

2^20605 mod 82421 = 68358

und

2^(2*20605) mod 82421 = 15891

wobei 20605 zustande kommt aus (82421-1) / 2^2 = 20605. Was habe ich für einen Fehler gemacht, bzw. nicht beachtet?

Thanks,

Wieland