Miller-Rabin

[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