Elliptic curves and primality proving

Atkin, A. O. L.; Morain, F.

doi:10.1090/S0025-5718-1993-1199989-X

Elliptic curves and primality proving
HTML articles powered by AMS MathViewer

by A. O. L. Atkin and F. Morain PDF

Math. Comp. 61 (1993), 29-68 Request permission

Abstract:

The aim of this paper is to describe the theory and implementation of the Elliptic Curve Primality Proving algorithm. Problema, numeros primos a compositis dignoscendi, hosque in factores suos primos resolvendi, ad gravissima ac utilissima totius arithmeticae pertinere, et geometrarum tum veterum tum recentiorum industriam ac sagacitatem occupavisse, tam notum est, ut de hac re copiose loqui superfluum foret.

References

Leonard Adleman, Kenneth Manders, and Gary Miller, On taking roots in finite fields, 18th Annual Symposium on Foundations of Computer Science (Providence, R.I., 1977) IEEE Comput. Sci., Long Beach, Calif., 1977, pp. 175–178. MR 0502224

Recognizing primes in random polynomial time

Leonard M. Adleman, Carl Pomerance, and Robert S. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. (2) 117 (1983), no. 1, 173–206. MR 683806, DOI 10.2307/2006975

The number of points on an elliptic curve modulo a prime

Elliptic curves and primality proving

A. O. L. Atkin and F. Morain, Finding suitable curves for the elliptic curve method of factorization, Math. Comp. 60 (1993), no. 201, 399–405. MR 1140645, DOI 10.1090/S0025-5718-1993-1140645-1

Elliptic pseudoprimes

Pierre Beauchemin, Gilles Brassard, Claude Crépeau, Claude Goutier, and Carl Pomerance, The generation of random numbers that are probably prime, J. Cryptology 1 (1988), no. 1, 53–64. MR 935901, DOI 10.1007/BF00206325
E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713–735. MR 276200, DOI 10.1090/S0025-5718-1970-0276200-X

Modular invariants expressible in terms of quadratic and cubic irrationalities

28

B. J. Birch, Weber’s class invariants, Mathematika 16 (1969), 283–294. MR 262206, DOI 10.1112/S0025579300008251
A. Borel, S. Chowla, C. S. Herz, K. Iwasawa, and J.-P. Serre, Seminar on complex multiplication, Lecture Notes in Mathematics, No. 21, Springer-Verlag, Berlin-New York, 1966. Seminar held at the Institute for Advanced Study, Princeton, N.J., 1957-58. MR 0201394

Primality testing using elliptic curves

Faster primality testing

Gilles Brassard, Modern cryptology, Lecture Notes in Computer Science, vol. 325, Springer-Verlag, New York, 1988. A tutorial. MR 962639

Some integer factorization algorithms using elliptic curves

8

John Brillhart, D. H. Lehmer, and J. L. Selfridge, New primality criteria and factorizations of $2^{m}\pm 1$, Math. Comp. 29 (1975), 620–647. MR 384673, DOI 10.1090/S0025-5718-1975-0384673-1
John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr., Factorizations of $b^n \pm 1$, 2nd ed., Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, RI, 1988. $b=2,3,5,6,7,10,11,12$ up to high powers. MR 996414, DOI 10.1090/conm/022
Duncan A. Buell, Small class numbers and extreme values of $L$-functions of quadratic fields, Math. Comp. 31 (1977), no. 139, 786–796. MR 439802, DOI 10.1090/S0025-5718-1977-0439802-X
J. P. Buhler, R. E. Crandall, and M. A. Penk, Primes of the form $n!\pm 1$ and $2\cdot 3\cdot 5\cdots p\pm 1$, Math. Comp. 38 (1982), no. 158, 639–643. MR 645679, DOI 10.1090/S0025-5718-1982-0645679-1
J. W. S. Cassels, Diophantine equations with special reference to elliptic curves, J. London Math. Soc. 41 (1966), 193–291. MR 199150, DOI 10.1112/jlms/s1-41.1.193
Danièle Chatelain, Bases normales de l’anneau des entiers de certaines extensions abéliennes de Q, C. R. Acad. Sci. Paris Sér. A-B 270 (1970), A557–A560 (French). MR 258802

An extension of Heilbronn’s class number theorem

5

Sequences of numbers generated by addition in formal groups and new primality and factorization tests

Cryptographic factorisation el primalité

l’utilisation des courbes elliptiques

H. Cohen and A. K. Lenstra, Implementation of a new primality test, Math. Comp. 48 (1987), no. 177, 103–121, S1–S4. MR 866102, DOI 10.1090/S0025-5718-1987-0866102-2
H. Cohen and H. W. Lenstra Jr., Primality testing and Jacobi sums, Math. Comp. 42 (1984), no. 165, 297–330. MR 726006, DOI 10.1090/S0025-5718-1984-0726006-X
Harvey Cohn, A classical invitation to algebraic numbers and class fields, Universitext, Springer-Verlag, New York-Heidelberg, 1978. With two appendices by Olga Taussky: “Artin’s 1932 Göttingen lectures on class field theory” and “Connections between algebraic number theory and integral matrices”. MR 506156
Harvey Cohn, Advanced number theory, Dover Books on Advanced Mathematics, Dover Publications, Inc., New York, 1980. Reprint of A second course in number theory, 1962. MR 594936
Harvey Cohn, Introduction to the construction of class fields, Cambridge Studies in Advanced Mathematics, vol. 6, Cambridge University Press, Cambridge, 1985. MR 812270

Su di un metodo per la risoluzione in numeri interi dell’ equazione

46

David A. Cox, Primes of the form $x^2 + ny^2$, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1989. Fermat, class field theory and complex multiplication. MR 1028322
M. Deuring, Die Klassenkörper der komplexen Multiplikation, Enzyklopädie der mathematischen Wissenschaften mit Einschluss ihrer Anwendungen, Band I 2, Heft 10, Teil II (Article I 2, vol. 23, B. G. Teubner Verlagsgesellschaft, Stuttgart, 1958 (German). MR 0167481

History of the theory of numbers

David R. Dorman, Special values of the elliptic modular function and factorization formulae, J. Reine Angew. Math. 383 (1988), 207–220. MR 921991, DOI 10.1515/crll.1988.383.207

Lehrbuch der Algebra

Carl Friedrich Gauss, Disquisitiones arithmeticae, Yale University Press, New Haven, Conn.-London, 1966. Translated into English by Arthur A. Clarke, S. J. MR 0197380

Über die praktische Auflösung von Gleichungen höheren Grades

Almost all primes can be quickly certified

Daniel M. Gordon, On the number of elliptic pseudoprimes, Math. Comp. 52 (1989), no. 185, 231–245. MR 946604, DOI 10.1090/S0025-5718-1989-0946604-2

Table of complex multiplication moduli

21

Benedict H. Gross, Arithmetic on elliptic curves with complex multiplication, Lecture Notes in Mathematics, vol. 776, Springer, Berlin, 1980. With an appendix by B. Mazur. MR 563921
Benedict H. Gross and Don B. Zagier, On singular moduli, J. Reine Angew. Math. 355 (1985), 191–220. MR 772491

Bignum

A portable and efficient package for arbitrary precision arithmetic

Factorization of polynomials over finite fields and factorization of primes in algebraic number fields

Riemann hypothesis and finding roots over finite fields

Kenneth F. Ireland and Michael I. Rosen, A classical introduction to modern number theory, Graduate Texts in Mathematics, vol. 84, Springer-Verlag, New York-Berlin, 1982. Revised edition of Elements of number theory. MR 661047

An improved Las Vegas primality test

Erich Kaltofen and Noriko Yui, Explicit construction of the Hilbert class fields of imaginary quadratic fields with class numbers $7$ and $11$, EUROSAM 84 (Cambridge, 1984) Lecture Notes in Comput. Sci., vol. 174, Springer, Berlin, 1984, pp. 310–320. MR 779136, DOI 10.1007/BFb0032853

Explicit construction of the Hilbert class fields of imaginary quadratic fields by integer lattice reduction

Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
Serge Lang, Elliptic functions, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London-Amsterdam, 1973. With an appendix by J. Tate. MR 0409362

Algorithms in number theory

Arjen K. Lenstra and Mark S. Manasse, Factoring by electronic mail, Advances in cryptology—EUROCRYPT ’89 (Houthalen, 1989) Lecture Notes in Comput. Sci., vol. 434, Springer, Berlin, 1990, pp. 355–371. MR 1083962, DOI 10.1007/3-540-46885-4_{3}5

Elliptic curves and number theoretic algorithms

H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649–673. MR 916721, DOI 10.2307/1971363
J.-F. Mestre, La méthode des graphes. Exemples et applications, Proceedings of the international conference on class numbers and fundamental units of algebraic number fields (Katata, 1986) Nagoya Univ., Nagoya, 1986, pp. 217–242 (French). MR 891898

Computing j via

Preda Mihailescu, A primality test using cyclotomic extensions, Applied algebra, algebraic algorithms and error-correcting codes (Rome, 1988) Lecture Notes in Comput. Sci., vol. 357, Springer, Berlin, 1989, pp. 310–323. MR 1008509, DOI 10.1007/3-540-51083-4_{6}8
I. Miyamoto and M. Ram Murty, Elliptic pseudoprimes, Math. Comp. 53 (1989), no. 187, 415–430. MR 970701, DOI 10.1090/S0025-5718-1989-0970701-9
Peter L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), no. 177, 243–264. MR 866113, DOI 10.1090/S0025-5718-1987-0866113-7

Implementation of the Atkin-Goldwasser-Kilian primality testing algorithm

Construction of Hilbert class fields of imaginary quadratic fields and dihedral equations modulo p

Résolution d’équations de petit degré modulo de grands nombres premiers

Solving generalized dihedral equations

Distributed primality proving and the primality of

François Morain, Elliptic curves, primality proving and some titanic primes, Astérisque 198-200 (1991), 245–251 (1992). Journées Arithmétiques, 1989 (Luminy, 1989). MR 1144327

Prime values of partition numbers and the primality of

On Cornacchia’s algorithm

François Morain and Jorge Olivos, Speeding up the computations on an elliptic curve using addition-subtraction chains, RAIRO Inform. Théor. Appl. 24 (1990), no. 6, 531–543 (English, with French summary). MR 1082914, DOI 10.1051/ita/1990240605311
Morris Newman, Daniel Shanks, and H. C. Williams, Simple groups of square order and an interesting sequence of primes, Acta Arith. 38 (1980/81), no. 2, 129–140. MR 604229, DOI 10.4064/aa-38-2-129-140
Andrew Ogg, Modular forms and Dirichlet series, W. A. Benjamin, Inc., New York-Amsterdam, 1969. MR 0256993
A. R. Rajwade and J. C. Parnami, A new cubic character sum, Acta Arith. 40 (1981/82), no. 4, 347–356. MR 667045, DOI 10.4064/aa-40-4-347-356
Carl Pomerance, Very short primality proofs, Math. Comp. 48 (1987), no. 177, 315–322. MR 866117, DOI 10.1090/S0025-5718-1987-0866117-4
Dimitrios Poulakis, Évaluation d’une somme cubique de caractères, J. Number Theory 27 (1987), no. 1, 41–45 (French). MR 904006, DOI 10.1016/0022-314X(87)90049-7
Vaughan R. Pratt, Every prime has a succinct certificate, SIAM J. Comput. 4 (1975), no. 3, 214–220. MR 391574, DOI 10.1137/0204018
A. R. Rajwade, Certain classical congruences via elliptic curves, J. London Math. Soc. (2) 8 (1974), 60–62. MR 338001, DOI 10.1112/jlms/s2-8.1.60
A. R. Rajwade, The Diophantine equation $y^{2}=x(x^{2}+21Dx+112D^{2})$ and the conjectures of Birch and Swinnerton-Dyer, J. Austral. Math. Soc. Ser. A 24 (1977), no. 3, 286–295. MR 472828, DOI 10.1017/s1446788700020309
Paulo Ribenboim, The book of prime number records, 2nd ed., Springer-Verlag, New York, 1989. MR 1016815, DOI 10.1007/978-1-4684-0507-1
Neil W. Rickert, Efficient reduction of quadratic forms, Computers and mathematics (Cambridge, MA, 1989) Springer, New York, 1989, pp. 135–139. MR 1005969, DOI 10.1007/978-1-4613-9647-5_{1}7
Reinhard Schertz, Die singulären Werte der Weberschen Funktionen $\mathfrak {f},\mathfrak {f}sb{1},\mathfrak {f}_{2},$ $\gamma _{2},$ $\gamma _{3}$, J. Reine Angew. Math. 286(287) (1976), 46–74 (German). MR 422213, DOI 10.1515/crll.1976.286-287.46
René Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp. 44 (1985), no. 170, 483–494. MR 777280, DOI 10.1090/S0025-5718-1985-0777280-6
Jean-Pierre Serre, Cours d’arithmétique, Collection SUP: “Le Mathématicien”, vol. 2, Presses Universitaires de France, Paris, 1970 (French). MR 0255476
Daniel Shanks, Class number, a theory of factorization, and genera, 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969) Amer. Math. Soc., Providence, R.I., 1971, pp. 415–440. MR 0316385
Daniel Shanks, Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1972) Congressus Numerantium, No. VII, Utilitas Math., Winnipeg, Man., 1973, pp. 51–70. MR 0371855
Goro Shimura and Yutaka Taniyama, Complex multiplication of abelian varieties and its applications to number theory, Publications of the Mathematical Society of Japan, vol. 6, Mathematical Society of Japan, Tokyo, 1961. MR 0125113
H. M. Stark, On the “gap” in a theorem of Heegner, J. Number Theory 1 (1969), 16–27. MR 241384, DOI 10.1016/0022-314X(69)90023-7

Une approche géométrique des algorithmes de réduction des réseaux en petite dimension

Ramanujans Vermutung über Zerfällungsanzahlen

179

Lehrbuch der Algebra

H. C. Williams, Primality testing on a computer, Ars Combin. 5 (1978), 127–185. MR 504864
H. C. Williams, Some primes with interesting digit patterns, Math. Comp. 32 (1978), no. 144, 1306–1310. MR 480311, DOI 10.1090/S0025-5718-1978-0480311-0
H. C. Williams, Effective primality tests for some integers of the forms $A5^n-1$ and $A7^n-1$, Math. Comp. 48 (1987), no. 177, 385–403. MR 866123, DOI 10.1090/S0025-5718-1987-0866123-X
H. C. Williams and Harvey Dubner, The primality of $R1031$, Math. Comp. 47 (1986), no. 176, 703–711. MR 856714, DOI 10.1090/S0025-5718-1986-0856714-3
H. C. Williams and C. R. Zarnke, Some algorithms for solving a cubic congruence modulo $p$, Utilitas Math. 6 (1974), 285–306. MR 389730
M. C. Wunderlich, A performance analysis of a simple prime-testing algorithm, Math. Comp. 40 (1983), no. 162, 709–714. MR 689483, DOI 10.1090/S0025-5718-1983-0689483-8