Miller-Rabin

[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