Test pierwszości Solovaya-Strassena

Test Solovaya-Strassenatest 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 testuEdytuj

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

 

gdzie   to symbol Legendre’a.

Symbol Legendre’a można uogólnić do symbolu Jacobiego   (gdzie   może być dowolną liczbą nieparzystą) i można badać czy kongruencja

 

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

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

 

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

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

 

jest świadkami Eulera. Dlatego też nie ma nieparzystej liczby złożonej   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ść czasowaEdytuj

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

Wejście:   wartość do testu pierwszości;

  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ć   razy:

wybrać   losowo ze zbioru  
 
jeżeli   lub   wtedy zwróć złożona.

zwróć prawdopodobnie pierwsza.

Używając szybkiego algorytmu potęgowania, czas działania algorytmu Solovaya-Strassena to   gdzie   to liczba losowań   natomiast   to liczba, której pierwszość jest testowana. (Warto zauważyć, że symbol Jacobiego może być obliczony w czasie   używając uogólnienia Jacobiego o prawie wzajemności reszt kwadratowych).

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

BibliografiaEdytuj

  • 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