Modernization of the Solovay-Strassen test

Abstract

Today’s version of the Solovay-Strassen test appears more complicated than the Miller-Rabin test mostly because of the need to compute the Jacobi symbol. This computation is required because the Solovay-Strassen test uses random numbers, which may possibly not be prime, as bases for the testing. However, choosing only prime numbers allows us to avoid the harder implementation of the Jacobi symbol and use instead the Legendre symbol. The calculation of the Legendre symbol can be performed by a simple procedure that computes the residue when a tested number is divided by a base.