Primzahlen berechnen mit nur wenigen Befehlen

[Apollonius]

Dann gibt es natürlich noch die probabilistischen Primzahltests. Dort können als prim angegebene Zahlen noch mit einer geringen Wahrscheinlichkeit zusammengesetzt sein. Dafür sind diese Tests extrem schnell. Die Fehlerwahrscheinlichkeit kann man ziemlich stark verringern, indem man die Iterationszahl vergrößert. Beispielsweise ist beim Miller-Rabin-Test die Wahrscheinlichkeit, dass eine nicht-Primzahl als prim angegeben wird, bei zwanzig Iterationen geringer als ein Billionstel.