Solovay–Strassen primality test

The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen, is a probabilistic test to determine if a number is composite or probably prime. It has been largely superseded by the Baillie-PSW primality test and the Miller–Rabin primality test, but has great historical importance in showing the practical feasibility of the RSA cryptosystem. The Solovay–Strassen test is essentially a Euler-Jacobi pseudoprime test.

Euler proved that for any prime number p and any integer a,

where ${\displaystyle \left({\tfrac {a}{p}}\right)}$ is the Legendre symbol. The Jacobi symbol is a generalisation of the Legendre symbol to ${\displaystyle \left({\tfrac {a}{n}}\right)}$, where n can be any odd integer. The Jacobi symbol can be computed in time O((log n)²) using Jacobi's generalization of law of quadratic reciprocity.

...
Wikipedia