Test Solovaya-Strassena – test 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.

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 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.

• 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