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