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