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 | edytuj kod]

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

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 \Omicron (k \cdot \log^3n), 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 \Omicron ((\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[edytuj | edytuj kod]

  • 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