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 x^n-1 $\not\equiv$1 mod n, dann ist n nicht prim. -- Um Primalität zu beweisen, braucht man aber mehr als nur ein x^n-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)