Certyfikat 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.

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).

Niestety powyższy algorytm można oszukać, tak żeby zaakceptował liczbę złożoną. W tym celu można podać mu fałszywy rozkład na czynniki pierwsze n −1, w którym będą znajdowały się liczby złożone. Przykładowo załóżmy, że twierdzimy, że 85 jest pierwsza, podając świadka x= 4 i równanie 84=6×14 jako rozkład n −1. Wtedy:

• 4 jest względnie pierwsze z 85
• 4⁸⁵⁻¹ ≡ 1 (mod 85)
• 4^(85−1)/6 ≡ 16 (mod 85), 4^(85−1)/14 ≡ 16 (mod 85)

Algorytm wywnioskuje, że 85 jest pierwsza. Zauważmy, że nie możemy samodzielnie szukać rozkładu n −1 na czynniki pierwsze, ponieważ nie znamy algorytmu, który robi to w wielomianowym czasie.

Lepszym sposobem rozwiązania tego problemu jest udostępnienie certyfikatów pierwszości również dla każdego czynnika n −1: w tej samej postaci, ale mniejszych i łatwiejszych do sprawdzenia. Postępujemy w ten sposób rekurencyjnie, aż dojdziemy do czynników o których wiemy, że są pierwsze (np. do 2). Kompletny certyfikat ma wtedy postać drzewa ze znanymi liczbami pierwszymi w liściach. Przykładowe drzewo udowadniające że 229 jest liczbą pierwszą, może wyglądać tak:

• 229 (x=6, 229−1 = 2²×3×19)
  • 2 (znana liczba pierwsza)
  • 3 (x=2, 3−1 = 2)
    • 2 (znana liczba pierwsza)
  • 19 (x=2, 19−1 = 2×3²)
    • 2 (znana liczba pierwsza)
    • 3 (x=2, 3−1 = 2)
      • 2 (znana liczba pierwsza)

Zauważmy, że iloczyn liczb na każdym poziomie drzewa jest nie większy niż początkowa liczba, a więc drzewo ma rozmiar liniowy. Liczba poziomów jest logarytmiczna, ponieważ n −1 dzieli się przez 2 dla wszystkich nieparzystych liczb pierwszych. Tym samym weryfikacja całego drzewa jest trwa co najwyżej O(log n) razy dłużej niż pierwotny algorytm.

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.

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Primality Certificate, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).
• Eric W.E.W. Weisstein Eric W.E.W., Pratt Certificate, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).
• Eric W.E.W. Weisstein Eric W.E.W., Atkin-Goldwasser-Kilian-Morain Certificate, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).
• Vašek Chvátal. Lecture notes on Pratt's Primality Proofs. Department of Computer Science. Rutgers University. PDF version at Concordia University.
• Wim van Dam. Proof of Pratt's Theorem. ^{[martwy link]}