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.
Certyfikaty Pratta Najbardziej znanymi certyfikatami pierwszości (choć nie pierwszymi wynalezionymi) są tzw. certyfikaty Pratta, wynalezione przez Pratta w 1975 r. Bazują one na odwróceniu małego twierdzenia Fermata z dodanym warunkiem, który uzupełnia to odwrócenie:
Załóżmy, że znamy liczbę całkowitą x taką że: x jest względnie pierwsza z n x n −1 ≡ 1 (mod n) Dla każdej liczby pierwszej p która dzieli n −1, nie zachodzi x(n −1)/p ≡ 1 (mod n). Wtedy n jest liczbą pierwszą
Znając taką liczbę x (nazywaną świadkiem) i rozkład na czynniki pierwsze n −1, powyższe warunki można szybko sprawdzić: wymaga to liniowej liczby działań na potęgach (bo każda liczba ma mniej dzielników pierwszych niż cyfr), z których każde wymaga O(log n) mnożeń (przy zastosowaniu szybkiego potęgowania).