Programming Praxis

We have seen the Miller-Rabin and Baillie-Wagstaff primality tests in previous exercises. Today we look at a test developed by Robert M. Solovay and Volker Strassen in 1977. The test is no longer used, having been superseded by the other two tests, but was historically of great importance in the development of the RSA cryptosystem.

The test is based on Euler’s Criterion, which states that a^(p−1)/2 ≡ (a / p) (mod p) for any odd prime number p and any integer a on the range 2 to p − 1 with gcd(a, p) = 1, where (a / p) is the Legendre symbol. If a number n being tested is prime, the test will indicate that n is prime; if a number n being tested is composite, the test will indicate that it is either prime or composite with equal likelihood, a coin flip. Thus, the Solovay-Strassen test chooses k different witnesses a; if any of them indicate n is composite, then it must be composite, but if none of them indicate n is composite, it is presumed prime with odds 2^−k.

If you are willing to assume the truth of the Extended Riemann Hypothesis, the Solovay-Strassen test can be made an absolute proof of primality by testing all prime a in the range 2 to min(n − 1, log² n); if none of the a indicate the compositeness of n, then n is prime on the ERH.

The Solovay-Strassen test is no longer used, for three reasons: First, it takes more work to implement, as it involves computing the Jacobi symbol as well as modular exponentiation, whereas the Miller-Rabin test involves only modular exponentiation. Second, the Miller-Rabin test has a better error bound, k⁻⁴ compared to k⁻². Third, all Euler witnesses are also Miller-Rabin strong witnesses to the compositeness of n. The presence of the absolute proof of primality on the ERH is also not a bar to the use of the Miller-Rabin test, as there is a similar proof of primality based on Miller-Rabin strong witnesses.

Your task is to write two versions of the Solovay-Strassen primality test, one probabilistic and one on the ERH. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2