On a Primality Test of Solovay and Strassen

Solovay and Strassen [SIAM J. Comput., 6 (1977), pp. 84–85] propose a primality test based on the fact that for primes $p > 2$ we have $(a/ p) \equiv a^{(p - 1)/2} (\bmod p)$, where $(a / p)$ is the Jacobi symbol. We prove here that the strong pseudoprime test is better, in the sense that it never takes more time nor is less effective, and sometimes is quicker or more effective. We also discuss the probability of error in the strong pseudoprime test, and show that it is never greater than $\tfrac{1}{4}$.