Primzahlgenerierung/-Test

Für RSA werden große Primzahlen p, q benötigt. Wo kommen die her? Würfeln und testen!

eine Primzahl hat keine nichttrivialen Faktoren.

Faktoren einer großen Zahl anzugeben ist schwer.

Feststellen, ob sie nichttriviale Faktoren hat, ist verhältnismäßig viel einfacher.

z. B. nach Satz von Fermat/Euler: wenn xn-1 $ \not\equiv$1 mod n, dann ist n nicht prim. -- Um Primalität zu beweisen, braucht man aber mehr als nur ein xn-1 $ \equiv$ 1 mod n.

Es gibt dafür schnelle probabilistische Verfahren (und seit ca. 2 Jahren sogar ein relativ schnelles, exaktes, siehe Primes is in P: http://www.cse.iitk.ac.in/news/primality.html)



Johannes Waldmann 2008-04-08