 Solovay–Strassen primality test

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.