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)(\mathrm{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)(\mathrm{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}\equiv ̸\left(\frac{a}{n}\right)(\mathrm{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}\mathrm{mod}n=x$ wtedy zwróć złożona.

zwróć prawdopodobnie pierwsza.

Używając szybkiego algorytmu potęgowania, czas działania algorytmu Solovaya-Strassena to $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 $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

• Szablon:Cytuj pismo
• 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