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 ${\displaystyle p}$ oraz dowolnej liczby naturalnej ${\displaystyle a}$ względnie pierwszej z ${\displaystyle p,}$

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

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

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

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

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

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

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

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

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

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

jest świadkami Eulera. Dlatego też nie ma nieparzystej liczby złożonej ${\displaystyle 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: ${\displaystyle n{:}}$ wartość do testu pierwszości;

${\displaystyle 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ć ${\displaystyle k}$ razy:

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

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

jeżeli ${\displaystyle x=0}$ lub ${\displaystyle 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 ${\displaystyle \mathrm {O} (k\cdot \log ^{3}n),}$ gdzie ${\displaystyle k}$ to liczba losowań ${\displaystyle a,}$ natomiast ${\displaystyle n}$ to liczba, której pierwszość jest testowana. (Warto zauważyć, że symbol Jacobiego może być obliczony w czasie ${\displaystyle \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 ${\displaystyle 2^{-k}.}$ Przy zastosowaniu w kryptografii, jeśli wybierze się dostatecznie duże ${\displaystyle 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