The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen in 1977, is a probabilistic primality test to determine if a number is composite or probably prime.
The idea behind the test was discovered by M. M. Artjuhov in 1967[1] (see Theorem E in the paper).
Euler proved[2] that for any odd prime number p and any integer a, where
This base a is called an Euler witness for n; it is a witness for the compositeness of n. The base a is called an Euler liar for n if the congruence is true while n is composite.
This contrasts with the Fermat primality test, for which the proportion of witnesses may be much smaller.
Therefore, there are no (odd) composite n without many witnesses, unlike the case of Carmichael numbers for Fermat's test.
Using an efficient method for raising a number to a power (mod n) such as binary exponentiation, we compute: This gives that, either 221 is prime, or 47 is an Euler liar for 221.
However, if the input n is composite then it is possible for the output to be incorrectly probably prime.
When n is odd and composite, at least half of all a with gcd(a,n) = 1 are Euler witnesses.
Hence the chance of the algorithm failing in this way is so small that the (pseudo) prime is used in practice in cryptographic applications, but for applications for which it is important to have a prime, a test like ECPP or the Pocklington primality test[3] should be used which proves primality.
On the average, the error probability of the algorithm is significantly smaller: it is less than for k rounds of the test, applied to uniformly random n ≤ x.
[4][5] The same bound also applies to the related problem of what is the conditional probability of n being composite for a random number n ≤ x which has been declared prime in k rounds of the test.
The Solovay–Strassen algorithm shows that the decision problem COMPOSITE is in the complexity class RP.