Test pierwszości Solovaya-Strassena

Test Solovaya-Strassena – test pierwszości opracowany przez Roberta M. Solovaya i Volkera Strassena. Jest to test probabilistyczny, który określa czy dana liczba jest liczbą złożoną, czy prawdopodobnie pierwszą. W większości zastosowań test ten został wyparty przez test Millera-Rabina, lecz ma wysoki historyczny wkład w pokazaniu praktycznego wykorzystania RSA.

Podstawa testu

Euler udowodnił, że dla liczby pierwszej $p$ oraz dowolnej liczby naturalnej $a$ względnie pierwszej z $p,$

$a^{(p-1)/2}\equiv \left({\frac {a}{p}}\right)\ (\operatorname {mod} \,p),$

gdzie $\left({\frac {a}{p}}\right)$ to symbol Legendre’a.

Symbol Legendre’a można uogólnić do symbolu Jacobiego $\left({\frac {a}{n}}\right),$ (gdzie $n$ może być dowolną liczbą nieparzystą) i można badać czy kongruencja

$a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right)\ (\operatorname {mod} \,n)$

jest spełniona dla różnych wartości $a.$ Jeżeli $n$ jest liczbą pierwszą, to powyższa kongruencja jest prawdziwa dla każdej wartości $a.$

Oznacza to, że $a$ jest świadkiem Eulera dla złożoności liczby $n$ jeśli:

$a^{(n-1)/2}\not \equiv \left({\frac {a}{n}}\right)\ (\operatorname {mod} \,n)$

Należy wybierać wartości $a$ losowo i sprawdzać czy liczba ta jest świadkiem Eulera dla $n.$ Jeśli zostanie znaleziony taki świadek Eulera, czyli takie $a,$ które nie spełnia kongruencji, to oznacza, że $n$ nie jest liczbą pierwszą (ale to nie mówi nic o nietrywialnym rozkładzie liczby $n$).

Użyteczność tego testu wynika z faktu, że dla każdej nieparzystej liczby złożonej $n$ przynajmniej połowa ze wszystkich

$a\in (\mathbb {Z} /n\mathbb {Z} )^{*}$

jest świadkami Eulera. Dlatego też nie ma nieparzystej liczby złożonej $n$ bez dużej ilości świadków złożoności, w przeciwieństwie do liczb Carmichaela w teście pierwszości Fermata.

Algorytm i złożoność czasowa

Algorytm można opisać następująco:

Wejście: $n{:}$ wartość do testu pierwszości;

$k{:}$ parametr określający dokładność testu.

Wyjście: złożona, jeśli n jest liczbą złożoną, w przeciwnym wypadku prawdopodobnie pierwsza;

powtórzyć $k$ razy:

wybrać $a$ losowo ze zbioru $\{2,3\dots ,n-1\}$

$x\leftarrow \left({\frac {a}{n}}\right),$

jeżeli $x=0$ lub $a^{(n-1)/2}\operatorname {mod} n\not =x$ wtedy zwróć złożona.

zwróć prawdopodobnie pierwsza.

Używając szybkiego algorytmu potęgowania, czas działania algorytmu Solovaya-Strassena to $\mathrm {O} (k\cdot \log ^{3}n),$ gdzie $k$ to liczba losowań $a,$ natomiast $n$ to liczba, której pierwszość jest testowana. (Warto zauważyć, że symbol Jacobiego może być obliczony w czasie $\mathrm {O} ((\log n)^{2})$ używając uogólnienia Jacobiego o prawie wzajemności reszt kwadratowych).

Prawdopodobieństwo błędnego wyniku tego algorytmu to $2^{-k}.$ Przy zastosowaniu w kryptografii, jeśli wybierze się dostatecznie duże $k,$ np. 100, szansa zajścia pomyłki jest tak mała, że można używać danej liczby jako pierwszej w programach kryptograficznych.

Bibliografia

• Solovay, Robert M. and Volker Strassen. A fast Monte-Carlo test for primality. „SIAM Journal on Computing”. 6 (1), s. 84–85, 1977. 
• Martin Dietzfelbinger, Primality Testing in Polynomial Time, From Randomized Algorithms to „PRIMES Is in P” (section 6), Series: Lecture Notes in Computer Science, Vol. 3000