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.

Contents

[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. The probability of failure of the Solovay-Strassen primality test is at most 1/2k, where k is the number of rounds.

[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 \mathcal O(k \times \log^3 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 at most 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.

[edit] Average-case behaviour

The bound 1/2 on the error probability of a single round of the Solovay–Strassen test holds for all inputs, but the numbers n for which the bound is (approximately) attained are extremely rare. On the average, the error probability of the algorithm is significantly smaller: it is less than 2^{-k}\exp\left(-(1+o(1))\frac{\log x\,\log\log\log x}{\log\log x}\right) for k rounds of the test, applied to uniformly random n ≤ x.[1][2] 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.

[edit] References

  1. ^ P. Erdős, C. Pomerance, On the number of false witnesses for a composite number, Mathematics of Computation 46 (1986), no. 173, pp. 259–279.
  2. ^ I. Damgård, P. Landrock, and C. Pomerance, Average case error estimates for the strong probable prime test, Mathematics of Computation 61 (1993), no. 203, pp. 177–194.
  • Solovay, Robert M. and Volker Strassen (1977). "A fast Monte-Carlo test for primality". SIAM Journal on Computing 6 (1): 84-85. doi:10.1137/0206006. 
  • 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
v • d • e
Number-theoretic algorithms
Primality tests
Sieving algorithms
Integer factorization algorithms
Other algorithms
Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests.