 Solovay–Strassen primality test

The Solovay-Strassen primality test samples unit bases and rejects an odd candidate as composite when it finds an Euler witness. Every prime passes every base by Euler's criterion, while an odd composite passes a random base with probability at most one half.

The Solovay–Strassen primality test is a probabilistic algorithm used to determine whether a given number is prime. It was developed independently by Robert Solovay and Jeffrey Strassen in the early 1970s. The test is based on properties of quadratic residues and the law of quadratic reciprocity. ### How the Test Works 1. **Input**: The algorithm takes an odd positive integer \( n \) greater than 1.