Primzahl ist eine natürliche Zahl größer 1, die nur durch sich selbst und 1 teilbar ist. Die Division ist also "glatt", sie hat keinen Rest.

Es gibt viele Theorien darüber, wie man möglist schnell feststellt, ob eine Zahl eine Primzahl ist oder nicht. Alle Methoden arbeiten mit einem mehr oder weniger mathematisch aufwendigen Verfahren zum Test auf Primzahleigenschaft. Es wird allerdings gesagt, daß die Prüfung einer Zahl n auf Primzahleingenschaft mit n < 1.000.000 am schnellsten durch Probieren aller Teiler t aus N von 1 < t < ist. Dies ist auch die einfachste und verbreitetste Methode.

Für die sichere Kryptographie werden allerdings Primzahlen größer 1.000.000 benötig. Zur Bestimmung von Primzahlen dieser Größenordung gibt es einige weitere Verfahren.

Zur Vertiefung ist [DEV94] und unten angegebener Link zu empfehlen.