Es wird allgemein empfohlen, probabilistische Primalitätstests durchzuführen, da diese sehr viel schneller sind, als vollstängig die Primalität zu zeigen. Mensch kann Primalitätstest verwenden, die mit einer bestimmten Fehlerwahrscheinlichkeit -sagen wir 2-100- prüfen, ob eine Zahl prim ist. Weiterführende Diskussionen dazu finden sind in [BBC88]. Empirische Ergebnisse für die Zuverlässigkeit einfacher Primalitätstests sind in [Riv91a] veröffentlicht. Danach ist es möglich, sehr schnelle Primalitätstests durchzuführen und äußerst sicher bzgl. der Ergebnisse zu sein. Ein einfacher Algorithmus zur Auswahl einer wahrscheinlichen Primzahl wurde von Brandt und Damgard [BD93b] analysiert.