Test pierwszości to algorytm , aby wiedzieć, czy całkowita jest prime .
Najprostszy test jest następujący: aby przetestować N , sprawdzamy, czy jest podzielna przez jedną z liczb całkowitych zawartych w szerokim znaczeniu między 2 a N-1. Jeśli odpowiedź jest negatywna, to N jest liczbą pierwszą, w przeciwnym razie jest złożona.
Kilka zmian poprawia wydajność tego algorytmu:
Testy probabilistyczne nie są testami pierwszości w ścisłym tego słowa znaczeniu (są częścią metod Monte-Carlo ): nie dają pewności, że liczba jest liczbą pierwszą, ale ich niski koszt w czasie obliczeń czyni je doskonałymi kandydatami do aplikacje w kryptologii często zależą w sposób krytyczny od dużych liczb pierwszych i akceptują współczynnik błędów pod warunkiem, że jest on bardzo niski: nazywane są one liczbami pierwszymi przemysłowymi (in) . Podstawowa idea testowania pierwszości liczby N jest następująca:
Po kilku iteracjach, jeśli N nie zostanie rozpoznane jako liczba złożona , zostanie zadeklarowana prawdopodobnie jako pierwsza .
Biorąc pod uwagę test, mogą istnieć pewne liczby złożone, które są określane jako „prawdopodobnie pierwsze” niezależnie od świadka. Takie liczby odporne na test nazywamy w tym teście liczbami pseudopierwszymi .
Najprostszym probabilistycznym testem pierwszości jest test pierwszości Fermata . Miller-Rabin test pierwszości i test pierwszości solovaya-strassena są bardziej wyrafinowane warianty, które wykrywają wszystkie związki. Każdy z tych testów jest używany, gdy wymagana jest liczba pierwsza po obliczeniu jak najkrótszym, przy jednoczesnym zaakceptowaniu niewielkiego marginesu wątpliwości, na przykład w szyfrowaniu RSA lub w protokole wymiany kluczy Diffie-Hellmana .
Test cyklotomiczny jest deterministycznym testem pierwszości; udowodnimy, że czas jego wykonania wynosi O ( n clog (log (n)) ), gdzie n jest liczbą cyfr N , a c jest stałą niezależną od n . Jego złożoność jest mniejsza niż wielomian .
Można wykazać, że test pierwszości krzywej eliptycznej uruchamia O ( n 6 ), ale tylko za pomocą pewnych przypuszczeń analitycznej teorii liczb, które nie zostały jeszcze udowodnione, ale powszechnie akceptowane jako prawdziwe. W praktyce test ten jest wolniejszy niż test cyklotomiczny dla liczb o więcej niż 10 000 cyfr.
Implementacja tych dwóch metod jest dość trudna, a zatem ryzyko błędu z powodu implementacji jest wyższe niż w przypadku metod probabilistycznych wymienionych powyżej.
Jeżeli uogólniona hipoteza Riemanna jest prawdziwa, test Millera-Rabina można przekształcić w wersję deterministyczną z czasem wykonania Õ ( n 4 ). W praktyce ten algorytm jest wolniejszy niż dwa poprzednie.
W 2002 roku Manindra Agrawal, Neeraj Kayal i Nitin Saxena opisali deterministyczny test pierwszości ( test pierwszości AKS ), który przebiega w ( n 12 ). Co więcej, zgodnie z przypuszczeniem (a więc nieudowodnionym, ale powszechnie uznawanym za prawdziwe), byłoby to wykonane w ( n 6 ). Jest to zatem pierwszy deterministyczny test pierwszości czasu wykonania wielomianu . W praktyce ten algorytm jest wolniejszy niż inne metody.
Teoria liczb dostarcza metod; dobrym przykładem jest test Lucasa-Lehmera sprawdzający, czy liczba jest liczbą pierwszą. Test ten jest powiązany z faktem, że wielokrotność pewnej liczby a modulo n wynosi n -1 dla liczby pierwszej n, gdy a jest pierwiastkiem pierwotnym . Jeśli możemy pokazać, że a jest pierwiastkiem pierwotnym dla n , możemy pokazać, że n jest liczbą pierwszą.
W teorii złożoności problem PRIMES to problem decyzji o przynależności do języka formalnego zawierającego liczby pierwsze, zapisane binarnie:
BONUS = {10, 11, 101, 111, 1011, ...}
gdzie 10, 11, 101, 111, 1011 ... są zapisami binarnymi liczb pierwszych 2, 3, 5, 7, 11 itd.
PRIMES jest w co-NP : rzeczywiście, jego komplementarne KOMPOZYTY, tj. decyzja o przynależności do zbioru liczb innych niż pierwsze, jest w NP , ponieważ możemy zdecydować ZŁOŻONE w czasie wielomianowym przez liczbę cyfr badanej liczby , na niedeterministycznej maszynie Turinga , zgadując czynnik.
W 1975 roku Vaughan Pratt (en) wykazał, że istnieje certyfikat na PREMIUM weryfikowalny w czasie wielomianowym. Zatem PRIMES jest również w NP, a więc w NP ∩ coNP .
Algorytmy Solovay – Strassen i Miller – Rabin pokazują, że PRIMES jest w coRP . W 1992 roku algorytm Adleman – Huang pokazuje, że PRIMES jest w RP . Zatem PRIMES jest w ZPP = RP ∩ coRP .
Test pierwszości Adleman – Pomerance – Rumely (en) z 1983 r. pokazuje, że PRIMES jest w QP (czasie quasi-wielomianowym), klasie, której nie wykazano, aby była porównywalna z jedną z wyżej wymienionych klas.
Test pierwszości AKS jest algorytmem czasu wielomianowego i ostatecznie pokazuje, że PREMIUMS jest w P . Ale PRIMES nie okazał się być P-kompletny . Nie wiemy, czy PRIMES jest na przykład w NC czy w LOGSPACE . Ale wiemy, że PRIMES nie jest w AC 0 .