Test pierwszości Solovaya-Strassena

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 testu[edytuj]

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ść czasowa[edytuj]

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.

Bibliografia[edytuj]

  • 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