An improved Las Vegas primality test

摘要

We present a modification of the Goldwasser-Kilian-Atkin primality test, which, when given an input n, outputs either prime or composite, along with a certificate of correctness which may be verified in polynomial time. Atkin's method computes the order of an elliptic curve whose endomorphism ring is isomorphic to the ring of integers of a given imaginary quadratic field Q(√---D). Once an appropriate order is found, the parameters of the curve are computed as a function of a root modulo n of the Hilbert class equation for the Hilbert class field of Q(√---D). The modification we propose determines instead a root of the Watson class equation for Q(√---D) and applies a transformation to get a root of the corresponding Hilbert equation. This is a substantial improvement, in that the Watson equations have much smaller coefficients than do the Hilbert equations.