The Soloway-Strassen Algorithm

Further information on this subject may be found in the book by Goodrich and Tamassia at http://ww3.algorithmdesign.net. The approach to primality testing is as follows. Let n be an odd integer that we want to test for primality, and let witness(x,n) be a Boolean function of a random variable x and n with the following properties:

1. If n is prime, then witness(x,n) is always false. So if witness(x,n) is true then n is definitely composite.
2. If n is composite, then witness(x,n) is false with probability q < 1.

A generic probabilistic primality testing algorithm is shown below. In order to turn this template into a full program, we need only specify the details of how to pick random numbers and compute witness(x,n).

The Soloway-Strassen algorithm is a specialisation of this template method. The composite witness function is based on the following number theoretic facts.

If (a|n) denotes the Jacobi symbol, then for any element a of Z_n, we have

(a|n) ≡ a^{(n - 1)/2} (mod n).

when n is prime. If n is composite, there may still be values of a such that the above equation is satisfied. If the equation is satisfied, we say that n is an Euler pseudo-prime with base a.

Lemma: Let n be a composite number. There are at most (n - 1)/2 positive values of a in Z_n such that n is an Euler pseudo-prime with base a.

The Soloway-Strassen primality testing algorithm uses the following compositeness witness function:

witness(x,n) =	/	false if n is an Euler pseudo-prime with base x
	\	true otherwise,

where x is a random integer with 1 < x ≤ n - 1. By the lemma, this function has error probability q ≤ 1/2.

Theorem: Given an odd positive integer n and a confidence parameter k > 0, the Soloway-Strassen algorithm determines whether n is prime with error probability 2^-k by performing O(k log n) arithmetic operations.

Click button on browser toolbar to restart computation

--- BACK ---