Test pierwszości Solovaya-Strassena , opracowany przez Roberta Solovaya i Volkera Strassena , jest testem pierwszości , czyli procesem, który określa, czy liczba nieparzysta jest liczbą złożoną, czy pierwszą . Jest to test probabilistyczny , gwarantujący prymat liczby badanej tylko z pewnym prawdopodobieństwem (które możemy obliczyć tak blisko 1, jak chcemy).
Test Solowaya-Strassena opiera się na pewnych podstawach teorii liczb , przypomnianych poniżej.
Legendre'a symbol jest zdefiniowany p sile od 0 jeśli jest wielokrotnością p , 1 gdy jest modulo p kwadratowy i -1 inaczej.
Niech n będzie nieparzysta liczba całkowita większa od 2, a n = jego czynniki pierwsze. Następnie przez cały The symbol Jacobiego jest uogólnieniem symbolu Legendre'a które warto :, gdzie są symbolami Legendre.
W przypadku symbolu Legendre, to znaczy dla dowolnej nieparzystej liczby pierwszej p , mówi to kryterium Eulera . Jest to tym bardziej prawdziwe, jeśli zastąpimy symbol Legendre symbolem Jacobiego. Jednak symbol Jacobiego można obliczyć dla całości w szybki sposób (stosując proste uogólnienie prawa kwadratowej wzajemności ).
Aby określić, czy dana nieparzysta liczba całkowita jest liczbą pierwszą, możemy sprawdzić, dla dużej liczby losowych wartości , czy zgodność
jest spełniony. Jeśli dla pewnej liczby całkowitej jest fałszem , wiemy, że nie jest to liczba pierwsza.
Jednak, podobnie jak w przypadku testu pierwszości Fermata , istnieją „kłamcy”. Wartość nazywana jest kłamcą Eulera, jeśli równość jest spełniona, chociaż n jest złożona. Euler świadkiem jest wartością , dla których równość nie jest spełniony, a zatem jest świadectwem tego, że n jest związek.
W przeciwieństwie do testu pierwszości Fermata dla każdego kompozytu całkowitej N , co najmniej połowę wszystkich z oznaczają kontrole Eulera. Dlatego nie ma wartości n, dla której wszyscy są kłamcami, podczas gdy istnieje dla liczb Carmichaela w teście Fermata.
Algorytm można zapisać w następujący sposób:
Dane wejściowe : n : nieparzysta liczba całkowita, której pierwotność chcemy poznać; k : maksymalna liczba obliczeń symbolu Jacobiego. Wyjście : złożone, jeśli n jest złożone, w przeciwnym razie prawdopodobnie jest liczbą pierwszą powtórz k razy: losowo wybierz między 2 a n - 1 jeśli x = 0 lub tak, zwraca związek prawdopodobnie wróci pierwszyKorzystając z szybkich algorytmów potęgowania modularnego , najgorszym przypadkiem złożoności czasowej tego algorytmu jest O ( k × log 3 n ), gdzie k to maksymalna liczba przypadków, w których losowo wyciągamy liczbę całkowitą, aby obliczyć z nią symbol Jacobiego, a n to wartość, której pierwotność chcemy zbadać. Prawdopodobieństwo, że algorytm nie powiedzie, to prawdopodobieństwo, że n składa się wiedząc, że algorytm mówi, że to pierwsza, jest mniejsza niż z (a nie 2 -m jak znaleźć w niektórych autorów, co jest w rzeczywistości prawdopodobieństwo, że algorytm odpowiada, że n jest liczbą pierwszą, a nie. Istnieją dwa rzędy wielkości między tymi dwoma prawdopodobieństwami dla typowych wartości n !)
W zastosowaniach kryptograficznych , jeśli wybierzemy wystarczająco dużą wartość k , na przykład 100, prawdopodobieństwo, że algorytm jest błędny, jest tak małe, że możemy bez obaw uznać liczbę, która przeszła test, jako liczbę pierwszą i wykorzystać ją w zastosowaniach kryptograficznych.
Od 1980 r. Test Solovaya-Strassena został w praktyce zastąpiony testem pierwszości Millera-Rabina , który jest bardziej skuteczny, ponieważ opiera się na podobnym kryterium, ale daje fałszywie dodatni wynik tylko raz na cztery razy, gdy n nie jest liczbą pierwszą.
Jeśli uogólniona hipoteza Riemanna , nie udowodniona w 2020 r., Jest prawdziwa, to każda liczba złożona przyznaje świadkowi Eulera mniej niż . Test pierwszości Solovaya-Strassena można w tym przypadku zaadaptować do deterministycznego testu złożoności , a zatem wielomian w liczbie cyfr .