An improved Las Vegas primality test

ABSTRACT

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.

REFERENCES

• 1: S Goldwasser , J Kilian, Almost all primes can be quickly certified, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.316-329, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12162]
• 2: D.Husem611er, Elliptic Curves, Springer GTM 111, 1987
• 3: Erich Kaltofen , Noriko Yui, Explicit Construction of the Hilbert Class Fields of Imaginary Quadratic Fields with Class Numbers 7 and 11, Proceedings of the International Symposium on Symbolic and Algebraic Computation, p.310-320, July 09-11, 1984
• 4: E.Kaltofen and N.Yui, "Explicit construction of the Hilbert class fields of imaginary quadratic fields by integer lattice reduction", New York Number Theory, Lec. Notes Malh.,Springer Verlag, to appear, 1989
• 5: A.K.Lenstra and H.W.Lenstra jr., "Algorithms in Number Theory", in Handbook of Theoretical Science, North Holland, Amsterdam 1987
• 6: H.W.Lenstra Jr., "Factoring integers with elliptic curves", Annals of Math, 126, 1987, pp.649-673
• 7: F.Morain, "Implementation of the Gotdwasser-Kilian- Atkin Primality Testing Algorithm", (Draft), University of Limoges, 1988
• 8: J.H.Silverman, The Arithmetic of Elliptic Curves, Springer GTM 106, 1986
• 9: G.N.Watson, "Singular Moduli (4)', Acta Arithmetica i (1035), p p.284-323

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Hyperbolic equations

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Theory