Test pierwszości

Test pierwszości to algorytm , aby wiedzieć, czy całkowita jest prime .

Metoda naiwna

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

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:

  1. Losowo narysuj liczbę a .
  2. Sprawdź pewną tożsamość, która obejmuje a, jak również podaną liczbę N i która jest prawdziwa, jeśli liczba N jest liczbą pierwszą. Jeśli tożsamość nie jest spełniony, to N jest koniecznie związek i test zatrzymuje się; w tym przypadku a nazywa się świadkiem testowym .
  3. Powtarzaj krok 1 aż do osiągnięcia żądanego marginesu niepewności.

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 .

Szybkie testy deterministyczne

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.

Metody oparte na teorii liczb

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

Teoria złożoności

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 .

Uwagi i referencje

  1. Vaughan Pratt. „Każdy prime ma zwięzły certyfikat”. SIAM Journal on Computing , obj. 4, s. 214–220. 1975. Cytaty , Pełny tekst .
  2. Michael O Rabin , „  Algorytm probabilistyczny do testowania pierwszości  ”, Journal of Number Theory , tom.  12, n o  1,1 st lutego 1980, s.  128–138 ( ISSN  0022-314X , DOI  10.1016 / 0022-314X (80) 90084-0 , odczyt online , dostęp 9 lipca 2019 ).
  3. Adelman i Huang 1992 .
  4. Leonard M. Adleman , Carl Pomerance i Robert S. Rumely , „  O odróżnianiu liczb pierwszych od liczb złożonych  ”, Annals of Mathematics , tom.  117 n o  1,1983, s.  173-206 ( ISSN  0003-486X , DOI  10.2307 / 2006975 , przeczytane online , dostęp 9 lipca 2019 ).
  5. „  QP w sprawie złożoności zoo  ” .
  6. (en-US) „  PRIMES jest w P | Annals of Mathematics  ” (dostęp 9 lipca 2019 r . ) .
  7. Allender, Saks i Szparliński 2001 .

Załączniki

Bibliografia

Ta książka zawiera wiele algorytmów napisanych w Rubim . Prezentacja tej edycji różni się od poprzedniej i jest skierowana do szerszego grona odbiorców.

Powiązane artykuły

Linki zewnętrzne