The Solovay-Strassen primality test is a probabilistic test to determine if a number is composite or probably prime.

Concepts

Euler proved that for a prime number p,

where

is the Legendre symbol.

Thus, if we have a value p and want to determine if it is prime, we can check many random values of a and make sure the above equality holds. If it does not hold for some a, we know that p must not be prime.

Much like with the Fermat primality test, however, there are liars. A value, a is known as an Euler liar if the equality holds and p is composite. An Euler witness is a value of a such that the equality does not hold when p is composite -- that is to say that a is a witness for the compositeness of p.

Unlike the Fermat primality test, for every composite p at least half of all

are Euler witnesses. Therefore, there are no such values that are guaranteed to be liars all the time, like Carmichael numbers are for Fermat's test.

Algorithm and running time

The algorithm can be written as follows:

Inputs: n: a value to test for primality; k: a parameter that determines the number of times to test for primality

Output: composite if n is composite, otherwise probably prime

repeat k times:

x ← (a/n)

if x = 0 or a^{(n − 1)/2} mod n ≠ x then return composite

return probably prime

Using fast algorithms for modular exponentiation, the running time of this algorithm is O(k × log³p), where k is the number of times we test a random a, and p is the value we want to test for primality. The probability of the algorithm failing is 2^-k. For purposes of cryptography if we pick a sufficiently large value of k, such as 100, the chance of the algorithm failing is so small that we can use the prime in cryptographic applications without worrying.