Test pierwszości Solovaya-Strassena

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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) \pmod p

gdzie \left(\frac{a}{p}\right) to Symbol Legendre'a.

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

 a^{(n-1)/2} \equiv \left(\frac{a}{n}\right) \pmod 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.

Powiemy, ż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) \pmod n

Wybierajmy wartości a losowo i sprawdzajmy czy liczba a jest świadkiem Eulera dla n. Jeśli znajdziemy świadka Eulera (czyli takie a które nie spełnia kongruencji), to wiemy, ż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:
wybierz losowo a z przedziału [2,n-1]
x\left(\frac{a}{n}\right)
jeżeli x = 0 lub a(n − 1)/2 mod nx wtedy zwróć złożona
zwróć prawdopodobnie pierwsza

Używając szybkiego algorytmu potęgowania, czas działania tego algorytmu to O(k × log3n), gdzie k to ile razy wybieraliśmy losowe a, oraz n to liczba, której pierwszość testujemy. (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 naszego algorytmu to 2-k. Dla użytku w kryptografii jeśli wybierzemy dostatecznie duże k, jak np. 100, szansa pomyłki algorytmu jest tak mała, że możemy 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