W której dziedzinie są wykorzystywane certyfikaty pierwszości?

W teorii liczb, certyfikat pierwszości albo dowód pierwszości to zwięzły formalny dowód, że dana liczba jest pierwsza, który można szybko zweryfikować – w przeciwieństwie do czasochłonnego przeprowadzenia testu pierwszości. Istnienie certyfikatów pierwszości dowiodło, że problem znajdowania liczb pierwszych leży w klasie NP: problemów których rozwiązania można sprawdzić w czasie wielomianowym.

Najbardziej znanymi certyfikatami pierwszości (choć nie pierwszymi wynalezionymi) sa tzw. certyfikaty Pratta, wynalezione przez Pratta w 1975 r. W praktyce generowanie certyfikatów Pratta dla dużych liczb jest trudne do zrealizowania, ponieważ wymaga rozłożenia na czynniki pierwsze n −1. W szczególnych wypadkach jest to łatwe (np. dla liczb Fermata), ale w ogólności używa się certyfikatów łatwiejszych do wygenerowania takich jak certyfikaty Atkin-Goldwasser-Kilian-Morain.