Solovay-Strassen primality test

The Solovay-Strassen primality test, developed by Robert M. Solovay and Volker Strassen in 1977, is a probabilistic primality test that decides whether a number is composite or probably prime. The underlying idea had been discovered by M. M. Artjuhov in 1967. It rests on Euler's result that for an odd prime p, a raised to (p-1)/2 is congruent modulo p to the Legendre symbol of a over p, generalized to the Jacobi symbol for any odd n. Given an odd number n and a randomly chosen base a, the test checks the congruence; a base that fails it is an Euler witness proving n composite, while a base that passes for a composite n is an Euler liar. For every odd composite number at least half of the bases are witnesses, so repeated random trials make a wrong answer unlikely. The test shows that the decision problem COMPOSITE lies in the complexity class RP. It has largely been superseded by the Baillie-PSW and Miller-Rabin tests but was historically important in showing that the RSA cryptosystem was practical.