Przykładowe drzewo udowadniające że 229 jest liczbą pierwszą, może wyglądać tak:

229 (x=6, 229−1 = 22×3×19) 2 (znana liczba pierwsza) 3 (x=2, 3−1 = 2) 2 (znana liczba pierwsza) 19 (x=2, 19−1 = 2×32) 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

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.

Kategoria:Algorytmiczna teoria liczb