Test pierwszości Solovay-Strassena

Z Wikipedii

Test Solovay-Strassena – test pierwszości opracowany przez Roberta M. Solovay'a 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.

[edytuj] Podstawa testu

Euler udowdonił, że dla liczby pierwszej p oraz dowolnej liczby naturalnej $a$ ,

$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,

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

wybierz losowo a z przedziału [1,n-1]

x ← $\left(\frac{a}{n}\right)$

jeżeli x = 0 lub a^{(n − 1)/2} mod n ≠ x wtedy zwróć złożona

zwróć prawdopodobnie pierwsza

Używając szybkiego algorytmu potęgowania, czas działania tego algorytmu to O(k × log³n), gdzie k to ile razy wybieraliśmy losowe a, orazn to liczba, której pierwszość testujemy. (Warto zauważyć, że symbol Jacobiego może być obliczony w czasie O((log n)²) używając uogólnienia Jacobi'ego 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.

[edytuj] Źródła

Solovay, Robert M. and Volker Strassen. A fast Monte-Carlo test for primality. SIAM Journal on Computing, 6 (1), 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