Solovay–Strassen primality test

A randomized test for primality that compares a modular exponentiation with a Jacobi symbol. A failed comparison proves a number composite; repeated passes give a bounded probability of error.

Euler's criterion: For an odd prime, a number raised to half the prime minus one is congruent to its Legendre symbol modulo that prime. The test generalizes this prime-only identity by replacing the Legendre symbol with the Jacobi symbol.
Congruence relation: An equivalence relation stating that two integers have the same remainder upon division by a modulus. The test's central comparison is an equality of residue classes modulo the candidate.
Robert M. Solovay: An American mathematician who worked in set theory, number theory, and theoretical computer science. He co-developed the primality test with Volker Strassen.
Primality certificate: A finite proof object that can be checked efficiently to establish that an integer is prime. Unlike a test pass, a certificate can provide a deterministic, independently verifiable proof.
Jacobi symbol: An arithmetic function for coprime integers, defined by extending the Legendre symbol multiplicatively over a composite denominator. It supplies the symbol compared with the modular power in each test round.
Legendre symbol: A function that records whether an integer is a nonzero square modulo an odd prime. The Jacobi symbol used by the test extends this prime-modulus symbol to composite moduli.
Volker Strassen: A German mathematician known for major contributions to computational mathematics and complexity theory. He co-developed the test and helped establish randomized algorithms as a tool in number theory.
AKS primality test: A deterministic polynomial-time algorithm for deciding whether an integer is prime. AKS gives unconditional certainty, while this test offers a simpler randomized route.
Euler–Jacobi pseudoprime: An odd composite integer satisfying the Euler–Jacobi congruence for a chosen base. A witness fails to detect compositeness when the chosen base satisfies this congruence.
Fermat's little theorem: For a prime modulus, a number not divisible by it raised to one less than the prime is congruent to one. It provides the exponent relation from which prime-specific power tests are developed.

Linked from 5 pages