Primality Testing

This chapter discusses various modern algorithms for primality testing, including the Miller-Rabin test, the elliptic curve test, and the AKS test. The Miller-Rabin test also known as the strong pseudoprimality test, or more precisely, the Miller-Selfridge-Rabin test, is a fast and practical probabilistic primality test. Its probabilistic error can be reduced to as small as one desires, but not to zero. A serious problem with the Goldwasser-Kilian test is that Schoof's algorithm seems almost impossible to implement. The Goldwasser-Kilian algorithm begins by searching for a curve and computes its number of points, but the Atkin-Morain ECPP algorithm does exactly the opposite. The ef?ciency of the AKS algorithm for test primality does not have any obvious connections to that of integer factorization, although the two problems are related to each other. The ef?ciency of the AKS algorithm has not yet become a threat to the security of the factoring base such as the RSA cryptographic systems, since the security of RSA depends on the computational intractability of the Integer Factorization Problem.