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 i złożoność czasowa 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.
Bibliografia
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
Solovaya-Strassena Kategoria:Arytmetyka modularna