das Problem, für in Binärdarstellung gegebene Zahlen zu entscheiden, ob sie Primzahlen sind.

Für die Eingabe n wird die Rechenzeit in der Eingabelänge, also ⌈ld(n)⌉ gemessen. Die Erkennung von Primzahlen mit mehr als 1000 Binärstellen spielt in der Kryptoanalyse eine wichtige Rolle. Das Problem ist in NP und co-NP enthalten. Aus algorithmischer Sicht gibt es einen auch praktisch effizienten Algorithmus, der zeigt, daß das Komplement des Problems in RP enthalten ist. Unter der Annahme, daß die erweiterte Riemannsche Vermutung korrekt ist, gibt es sogar einen polynomialen Algorithmus (polynomialer Algorithmus) zur Primzahlerkennung.