Solovay-Strassen test


It is known that an odd numberMathworldPlanetmathPlanetmath n is prime if and only if for every 1<a<n such that (a,n)=1 we have

(an)an-12(modn) (1)

where (an) is the Jacobi symbolMathworldPlanetmath. (The only if part is obvious; the if part follows from Theorem 1.) From this we can derive the following algorithmMathworldPlanetmath.

  1. 1.

    Choose a random number a between 1 and n-1.

  2. 2.

    Check if (a,n)=1 (for example using the Euclidean algorithmMathworldPlanetmath). If it is not, then n is not prime and (a,n) is a divisorMathworldPlanetmathPlanetmath of n.

  3. 3.

    Check if Equation (1) holds. If it does not, then n is not prime. Otherwise n is a candidate for primality.

By repeating this algorithm we can increase the chance that the result is correct. In order to estimate the probability of error, we make use of Theorem 1, which says that every independent iteration of the algorithm has a chance of at most 50% of being wrong. Hence, after t iterations there is at most a 2-t chance of getting a wrong result.

Theorem 1.

Let n3 be an odd composite integer. Then at least half of the elements of Zn* do not satisfy Equation (1).

Proof.

It suffices to exhibit one element an* which does not satisfy Equation (1). Indeed, if there exists one such element, then the set of all elements which do satisfy Equation (1) forms a proper subgroupMathworldPlanetmath of n*, from which we conclude that the elements satisfying Equation (1) number no more than half of the elements of n*.

We consider separately the cases where n is squarefreeMathworldPlanetmath and not squarefree. If n is squarefree, let p be a prime dividing n and let b be a quadratic non-residue mod n. Using the Chinese Remainder TheoremMathworldPlanetmathPlanetmathPlanetmath, choose an integer an* such that:

a b(modp),
a 1(modnp).

The Jacobi symbol (an) is given by

(an)=(ap)(an/p)=(bp)(1n/p)=(-1)1=-1.

We will assume that an-12-1(modn) and derive a contradictionMathworldPlanetmathPlanetmath. The equation an-12-1(modn) implies that an-12-1(modnp). However, since a1(modnp), we must have an-121(modnp), so that 1-1(modnp), which is a contradiction.

Now suppose that n is not squarefree. Let p be a prime such that p2n, and set a=1+np. By the binomial theoremMathworldPlanetmath, we have

ap=(1+np)p=1+(p1)(n/p)+(p2)(n/p)2++(pp)(n/p)p1(modn),

so the multiplicative orderMathworldPlanetmath of amodn is equal to p, and hence in particular an-11(modn), since pn-1. On the other hand,

(an)=(1+npn)=(1+npp)(1+npn/p)=(1p)(1n/p)=1,

so a does not satisfy Equation (1). ∎

Title Solovay-Strassen test
Canonical name SolovayStrassenTest
Date of creation 2013-03-22 14:27:33
Last modified on 2013-03-22 14:27:33
Owner mathwizard (128)
Last modified by mathwizard (128)
Numerical id 7
Author mathwizard (128)
Entry type Algorithm
Classification msc 11Y11
Related topic MillerRabinPrimeTest