La primalité en temps polynomial

Morain, François

Séminaire Bourbaki : volume 2002/2003, exposés 909-923, Astérisque, no. 294 (2004), Exposé no. 917, pp. 205-230.

Le problème de la primalité est l'un des problèmes les plus simples et les plus anciens de la théorie des nombres. À la fin des années 1970, Adleman, Pomerance et Rumely ont donné le premier algorithme de primalité déterministe, dont le temps de calcul était presque polynomial. Il a fallu 20 années supplémentaires pour qu'Agrawal, Kayal et Saxena donnent un algorithme déterministe de temps de calcul polynomial. L'exposé présentera ces travaux, et il fera également le point sur les différents autres algorithmes inventés dans cette période.

Primality is one of the simplest and oldest problems in number theory. At the end of the seventies, Adleman, Pomerance and Rumely have designed the first deterministic primality proving algorithm, whose running time was quasi polynomial. Twenty years later, Agrawal, Kayal and Saxena gave the first algorithm running in polynomial time. The talk will present all these works, and will also include the description of some of the primality algorithms invented during this period.

[1] L. M. Adleman - “On distinguishing prime numbers from composite numbers”, in Foundations of computer science, IEEE, 1980, 21st FOCS, Syracuse, USA, Proceedings, p. 387-406. | Zbl

[2] L. M. Adleman & M.-D. A. Huang - Primality testing and Abelian varieties over finite fields, Lecture Notes in Math., vol. 1512, Springer-Verlag, 1992. | MR | Zbl

[3] L. M. Adleman, C. Pomerance & R. S. Rumely - “On distinguishing prime numbers from composite numbers”, Ann. of Math. (2) 117 (1983), p. 173-206. | MR | Zbl

[4] L. M. Adleman, R. L. Rivest & A. Shamir - “A method for obtaining digital signatures and public-key cryptosystems”, Comm. ACM 21 (1978), no. 2, p. 120-126. | MR | Zbl

[5] M. Agrawal & S. Biswas - “Primality and identity testing via chinese remaindering”, in Proc. Ann. IEEE Symp. Found. Comp. Sci., 1999, p. 202-209. | MR

[6] M. Agrawal, N. Kayal & N. Saxena - “PRIMES is in P”, Preprint ; available at http://www.cse.iitk.ac.in/primality.pdf, 2002. | MR | Zbl

[7] W. R. Alford, A. Granville & C. Pomerance - “There are infinitely many Carmichael numbers”, Ann. of Math. (2) 139 (1994), no. 3, p. 703-722. | MR | Zbl

[8] M. Artjuhov - “Certain criteria for the primality of numbers connected with the little Fermat theorem (russian)”, Acta Arith. 12 (1966/67), p. 355-364. | MR

[9] A. O. L. Atkin & F. Morain - “Elliptic curves and primality proving”, Math. Comp. 61 (1993), no. 203, p. 29-68. | MR | Zbl

[10] E. Bach - “Explicit bounds for primality testing and related problems”, Math. Comp. 55 (1990), no. 191, p. 355-380. | MR | Zbl

[11] R. C. Baker & G. Harman - “The Brun-Titschmarsh theorem on average”, in Proceedings of a conference in Honor of Heini Halberstam, vol. 1, 1996, p. 39-103. | MR | Zbl

[12] R. C. Baker, G. Harman & J. Pintz - “The difference between consecutive primes. II”, Proc. London Math. Soc. (3) 83 (2001), no. 3, p. 532-562. | MR | Zbl

[13] D. Bernstein - “An exposition of the Agrawal-Kayal-Saxena primality-proving theorem”, Preprint, 2002.

[14] -, “Proving primality after Agrawal-Kayal-Saxena”, http://cr.yp.to/papers/aks.ps, 2003.

[15] -, “Proving primality in essentially quartic expected time”, http://cr.yp.to/papers/quartic.ps, 2003.

[16] P. Berrizbeitia - “Sharpening “Primes is in P” for a large family of numbers”, http://arxiv.org/abs/math.NT/0211334, 2002. | MR | Zbl

[17] I. Blake, G. Seroussi & N. Smart - Elliptic curves in cryptography, London Math. Soc. Lecture Note Ser., vol. 265, Cambridge University Press, 1999. | MR | Zbl

[18] W. Bosma & M.-P. Van Der Hulst - “Primality proving with cyclotomy”, Thèse, Universiteit van Amsterdam, 1990.

[19] J. Brillhart, D. H. Lehmer & J. L. Selfridge - “New primality criteria and factorizations of $2^m\pm 1$”, Math. Comp. 29 (1975), no. 130, p. 620-647. | MR | Zbl

[20] J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman & S. S. Wagstaff, Jr. - Factorizations of $b^n\pm 1,b=2,3,5,6,7,10,11,12$ up to high powers, 2 'ed., Contemporary Mathematics, no. 22, AMS, 1988. | Zbl

[21] O. Caprotti & M. Oostdijk - “Formal and efficient primality proofs by use of computer algebra oracles”, J. Symbolic Comput. 32 (2001), p. 55-70. | MR | Zbl

[22] H. F. Chau & H.-K. Lo - “Primality test via quantum factorization”, Internat. J. Modern Phys. C 8 (1997), no. 2, p. 131-138. | MR | Zbl

[23] Q. Cheng - “Primality proving via one round in ECPP and one iteration in AKS”, in Advances in Cryptology - CRYPTO 2003 (D. Boneh, 'ed.), Lecture Notes in Comput. Sci., vol. 2729, Springer Verlag, 2003, p. 338-348. | MR | Zbl

[24] H. Cohen - A course in algorithmic algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, 1996, Third printing. | Zbl

[25] H. Cohen & A. K. Lenstra - “Implementation of a new primality test”, Math. Comp. 48 (1987), no. 177, p. 103-121. | MR | Zbl

[26] H. Cohen & H. W. Lenstra, Jr. - “Primality testing and Jacobi sums”, Math. Comp. 42 (1984), no. 165, p. 297-330. | MR | Zbl

[27] L. Comtet - Analyse combinatoire, Presses Universitaires de France, 1970. | MR | Zbl

[28] D. A. Cox - Primes of the form $x^2+n{y}^2$, John Wiley & Sons, 1989. | MR | Zbl

[29] R. Crandall & C. Pomerance - Prime numbers - a computational perspective, Springer Verlag, 2000. | MR | Zbl

[30] N. D. Elkies - “Elliptic and modular curves over finite fields and related computational issues”, in Computational Perspectives on Number Theory : Proceedings of a Conference in Honor of A.O.L. Atkin (D.A. Buell & J.T. Teitelbaum, éds.), AMS/IP Studies in Advanced Mathematics, vol. 7, American Mathematical Society, International Press, 1998, p. 21-76. | MR | Zbl

[31] E. Fouvry - “Théorème de Brun-Titschmarsh ; application au théorème de Fermat”, Invent. Math. 79 (1985), p. 383-407. | EuDML | MR | Zbl

[32] J. Franke, T. Kleinjung, F. Morain & T. Wirth - “Proving the primality of very large numbers with fastECPP”, in Algorithmic Number Theory (D. Buell, 'ed.), Lecture Notes in Comput. Sci., Springer Verlag, 2004, 6th International Symposium, ANTS-IV, Burlington, June 2004, Proceedings. | MR | Zbl

[33] J. Von Zur Gathen & J. Gerhard - Modern computer algebra, Cambridge University Press, 1999. | MR | Zbl

[34] P. Gaudry & R. Harley - “Counting points on hyperelliptic curves over finite fields”, in Algorithmic Number Theory (W. Bosma, 'ed.), Lecture Notes in Comput. Sci., vol. 1838, Springer Verlag, 2000, 4th International Symposium, ANTS-IV, Leiden, The Netherlands, July 2000, Proceedings, p. 313-332. | MR | Zbl

[35] M. Goldfeld - “On the number of primes $p$ for which $p+a$ has a large prime factor”, Mathematika 16 (1969), p. 23-27. | MR | Zbl

[36] S. Goldwasser & J. Kilian - “Almost all primes can be quickly certified”, in Proc. 18th STOC, ACM, 1986, May 28-30, Berkeley, p. 316-329.

[37] -, “Primality testing using elliptic curves”, Journal of the ACM 46 (1999), no. 4, p. 450-472. | MR

[38] D. R. Heath-Brown - “The differences between consecutive primes”, J. London Math. Soc. (2) 18 (1978), no. 1, p. 7-13. | MR | Zbl

[39] K. Ireland & M. Rosen - A classical introduction to modern number theory, Graduate Texts in Mathematics, vol. 84, Springer, 1982. | MR | Zbl

[40] H. Iwaniec & M. Jutila - “Primes in short intervals”, Ark. Mat. 17 (1979), no. 1, p. 167-176. | MR | Zbl

[41] N. Kayal & N. Saxena - “Towards a deterministic polynomial-time primality test”, Technical report, IIT Kanpur, 2002, http://www.cse.iitk.ac.in/research/btp2002/primality.html.

[42] D. E. Knuth - The Art of Computer Programming : Seminumerical algorithms, 2nd 'ed., Addison-Wesley, 1981. | MR | Zbl

[43] H. Lange & W. Ruppert - “Complete systems of addition laws on abelian variety”, Invent. Math. 79 (1985), p. 603-610. | EuDML | MR | Zbl

[44] D. H. Lehmer - “Strong Carmichael numbers”, J. Austral. Math. Soc. Ser. A 21 (1976), p. 508-510. | MR | Zbl

[45] A. K. Lenstra & H. W. Lenstra, Jr. - “Algorithms in number theory”, in Handbook of Theoretical Computer Science (J. van Leeuwen, 'ed.), vol. A : Algorithms and Complexity, North Holland, 1990, p. 674-715. | Zbl

[46] -(éds.) - The development of the number field sieve, Lecture Notes in Math., vol. 1554, Springer, 1993. | MR | Zbl

[47] H. W. Lenstra, Jr. - “Miller's primality test”, Inform. Process. Lett. 8 (1979), no. 2, p. 86-88. | MR | Zbl

[48] -, “Primality testing algorithms (after Adleman, Rumely, Williams)”, in Séminaire Bourbaki (1980/81), Lecture Notes in Math., vol. 901, Springer-Verlag, 1981, exposé no 576. | Numdam | MR | Zbl

[49] -, “Primality testing”, in Computational methods in number theory, Part I, Math. Centrum, Amsterdam, 1982, p. 55-77. | MR | Zbl

[50] -, “Primality testing with Artin symbols”, in Number theory related to Fermat's last theorem (Cambridge, Mass., 1981), Progr. Math., vol. 26, Birkhäuser Boston, Mass., 1982, p. 341-347. | MR | Zbl

[51] -, “Galois theory and primality testing”, in Orders and their applications (I. Reiner & K. W. Roggenkamp, éds.), Lecture Notes in Math., vol. 1142, Springer, 1984, Proc. of a conference, Oberwolfach, June 3-9, 1984, p. 169-189. | MR | Zbl

[52] -, “Elliptic curves and number-theoretic algorithms”, in Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Berkeley, Calif., 1986) (Providence, RI), Amer. Math. Soc., 1987, p. 99-120. | MR | Zbl

[53] -, “Factoring integers with elliptic curves”, Ann. of Math. (2) 126 (1987), p. 649-673. | MR | Zbl

[54] A. Menezes, P. C. Van Oorschot & S. A. Vanstone - Handbook of applied cryptography, CRC Press, 1997. | MR | Zbl

[55] P. Mihăilescu - “Cyclotomy of rings and primality testing”, Diss. ETH No. 12278, Swiss Federal Institute of Technology Zürich, 1997.

[56] P. Mihăilescu & R. Avanzi - “Efficient quasi-deterministic primality test improving AKS”, Available from http://www-math.uni-paderborn.de/~preda/papers/myaks1.ps, april 2003.

[57] G. L. Miller - “Riemann's hypothesis and tests for primality”, in Proc. 7th STOC, 1975, p. 234-239. | MR | Zbl

[58] F. Morain - “Calcul du nombre de points sur une courbe elliptique dans un corps fini : aspects algorithmiques”, J. Théor. Nombres Bordeaux 7 (1995), p. 255-282. | EuDML | Numdam | MR | Zbl

[59] -, “Implementing the asymptotically fast version of the elliptic curve primality proving algorithm”, Available at http ://www.lix.polytechnique.fr/Labo/Francois.Morain/, 2003. | Zbl

[60] C. H. Papadimitriou - Computational complexity, Addison-Wesley, 1995. | MR | Zbl

[61] C. Pomerance - “Analysis and comparison of some integer factoring algorithms”, in Computational methods in number theory (H.W. Lenstra, Jr. & R. Tijdeman, éds.), Mathematisch Centrum, Amsterdam, 1982, Mathematical Center Tracts 154/155, p. 89-140. | MR | Zbl

[62] -, “Very short primality proofs”, Math. Comp. 48 (1987), no. 177, p. 315-322. | MR

[63] C. Pomerance, J. L. Selfridge & S. S. Wagstaff, Jr. - “The pseudoprimes to $25.{10}^9$”, Math. Comp. 35 (1980), no. 151, p. 1003-1026. | MR | Zbl

[64] V. R. Pratt - “Every prime has a succint certificate”, SIAM J. Comput. 4 (1975), p. 214-220. | MR | Zbl

[65] M. Rabin - “Probabilistic algorithms for testing primality”, J. Number Theory 12 (1980), p. 128-138. | MR | Zbl

[66] J. Radhakrishnan - “Primes in P”, Bull. of the EATCS 78 (2002), p. 61-65.

[67] P. Ribenboim - The new book of prime number records, Springer-Verlag, 1996. | MR | Zbl

[68] J. B. Rosser & L. Schoenfeld - “Approximate formulas for some functions of prime numbers”, Illinois J. Math. 6 (1962), p. 64-94. | MR | Zbl

[69] R. Schoof - “Elliptic curves over finite fields and the computation of square roots mod $p$”, Math. Comp. 44 (1985), p. 483-494. | MR | Zbl

[70] -, “Counting points on elliptic curves over finite fields”, J. Théor. Nombres Bordeaux 7 (1995), p. 219-254. | EuDML | Numdam | MR | Zbl

[71] P. W. Shor - “Algorithms for quantum conputation : Discrete logarithms and factoring”, in Proceedings 26th Annual ACM Symposium on Theory of Computing (STOC) (Montreal, Canada), ACM, 1994, p. 124-134. | MR

[72] R. Solovay & V. Strassen - “A fast Monte-Carlo test for primality”, SIAM J. Comput. 6 (1977), no. 1, p. 84-85, Erratum, ibid, volume 7, 1, 1978. | MR | Zbl

[73] P. Van Wamelen - “Jacobi sums over finite fields”, Acta Arith. 102.1 (2002), p. 1-20. | EuDML | MR | Zbl

[74] E. Waterhouse - “Abelian varieties over finite fields”, Ann. Sci. École Norm. Sup. 2 (1969), p. 521-560. | EuDML | Numdam | MR | Zbl

[75] A. Weng - “Constructing hyperelliptic curves of genus 2 suitable for cryptography”, Math. Comp. 72 (2003), p. 435-458. | MR | Zbl

[76] H. C. Williams & J. O. Shallit - “Factoring integers before computers”, in Mathematics of Computation 1943-1993 : a half-century of computational mathematics (Vancouver, BC, 1993), Proc. Sympos. Appl. Math., vol. 48, Amer. Math. Soc., Providence, RI, 1994, p. 481-531. | MR | Zbl