Solovay-Strassen primality test

From Wikipedia, the free encyclopedia

The Solovay-Strassen primality test, developed by Robert M. Solovay and Volker Strassen, is a probabilistic test to determine if a number is composite or probably prime. It has been largely superseded by the Miller-Rabin primality test, but has great historical importance in showing the practical feasibility of the RSA cryptosystem.

[edit] Concepts

Euler proved that for a prime number p and any integer $a$ ,

$a^{(p-1)/2} \equiv \left(\frac{a}{p}\right) \pmod p$

where

$\left(\frac{a}{p}\right)$

is the Legendre symbol. The Jacobi symbol is a generalisation of the Legendre symbol to

$\left(\frac{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 law of quadratic reciprocity.

We can contemplate whether or not the congruence

$a^{(n-1)/2} \equiv \left(\frac{a}{n}\right) \pmod n$

holds for various values of a. 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).

Call a an Euler witness if the above congruence with the Jacobi symbol does not hold at a -- that is to say that a is a witness for the compositeness of n. Unlike the Fermat primality test, for every composite odd n at least half of all

$a \in (\mathbb{Z}/n\mathbb{Z})^*$

are (Euler) witnesses. Therefore, there are no (odd) composite n without lots of witnesses, unlike the case of Carmichael numbers for Fermat's test.

[edit] 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 accuracy of the test

Output: composite if n is composite, otherwise probably prime

repeat k times:

choose a at random in the interval [1,n-1]

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³n), where k is the number of times we test a random a, and n 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.