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 (see Theorem E in the paper). This test has been largely superseded by the Baillie–PSW primality test and the Miller–Rabin primality test, but has great historical importance in showing the practical feasibility of the RSA cryptosystem.
Concepts Euler proved that for any odd prime number p and any integer a,
a ( p − 1 ) / 2 ≡ ( a p ) ( mod p ) {\displaystyle a^{(p-1)/2}\equiv \left({\frac {a}{p}}\right){\pmod {p}}}
where ( a p ) {\displaystyle \left({\tfrac {a}{p}}\right)} is the Legendre symbol. The Jacobi symbol is a generalisation of the Legendre symbol to ( a n ) {\displaystyle \left({\tfrac {a}{n}}\right)} , where n can be any odd integer. The Jacobi symbol can be computed in time O((log n)²) using Jacobi's generalization of the law of quadratic reciprocity. Given an odd number n one can contemplate whether or not the congruence
a ( n − 1 ) / 2 ≡ ( a n ) ( mod n ) {\displaystyle a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}}
holds for various values of the "base" a, given that a is relatively prime to n. If n is prime then this congruence is true for all a. So if we pick values of a at random and test the congruence, then as soon as we find an a which doesn't fit the congruence we know that n is not prime (but this does not tell us a nontrivial factorization of n). 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. For every composite odd n, at least half of all bases
a ∈ ( Z / n Z ) ∗ {\displaystyle a\in (\mathbb {Z} /n\mathbb {Z} )^{*}}
are (Euler) witnesses as the set of Euler liars is a proper subgroup of ( Z / n Z ) ∗ {\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}} . For example, for n = 65 {\displaystyle n=65} , the set of Euler liars has order 8 and = { 1 , 8 , 14 , 18 , 47 , 51 , 57 , 64 } {\displaystyle =\{1,8,14,18,47,51,57,64\}} , and ( Z / n Z ) ∗ {\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}} has order 48. 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.
Example Suppose we wish to determine if n = 221 is prime. We write (n−1)/2=110. We randomly select an a (greater than 1 and smaller than n): 47. Using an efficient method for raising a number to a power (mod n) such as binary exponentiation, we compute:
a(n−1)/2 mod n = 47110 mod 221 = −1 mod 221
( a n ) mod n = ( 47 221 ) mod 2 21 = − 1 mod 2 21 {\displaystyle \left({\tfrac {a}{n}}\right){\bmod {n}}=\left({\tfrac {47}{221}}\right){\bmod {2}}21=-1{\bmod {2}}21}
This gives that, either 221 is prime, or 47 is an Euler liar for 221. We try another random a, this time choosing a = 2:
a(n−1)/2 mod n = 2110 mod 221 = 30 mod 221
… excerpt ends here. Continue reading the full article.
