La primalité en temps polynomial  [ Primality in polynomial time ]
Séminaire Bourbaki : volume 2002/2003, exposés 909-923, Astérisque, no. 294 (2004), Talk no. 917, p. 205-230

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.

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.

Classification:  11A41,  11Y11,  11Y16
Keywords: primality proving, Jacobi sums, elliptic curves, hyperelliptic curves, complex multiplication, finite fields
@incollection{SB_2002-2003__45__205_0,
     author = {Morain, Fran\c cois},
     title = {La primalit\'e en temps polynomial},
     booktitle = {S\'eminaire Bourbaki : volume 2002/2003, expos\'es 909-923},
     author = {Collectif},
     series = {Ast\'erisque},
     publisher = {Association des amis de Nicolas Bourbaki, Soci\'et\'e math\'ematique de France},
     address = {Paris},
     number = {294},
     year = {2004},
     note = {talk:917},
     pages = {205-230},
     zbl = {1097.11059},
     mrnumber = {2111645},
     language = {fr},
     url = {http://www.numdam.org/item/SB_2002-2003__45__205_0}
}
Morain, François. La primalité en temps polynomial, in Séminaire Bourbaki : volume 2002/2003, exposés 909-923, Astérisque, no. 294 (2004), Talk no. 917, pp. 205-230. http://www.numdam.org/item/SB_2002-2003__45__205_0/

[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 0526.10004

[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 1176511 | Zbl 0744.11065

[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 683806 | Zbl 0526.10004

[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 700103 | Zbl 0368.94005

[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 1917560

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

[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 1283874 | Zbl 0816.11005

[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 213289

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

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

[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 1399332 | Zbl 0853.11078

[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 1851081 | Zbl 1016.11037

[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 2164112 | Zbl 1071.11071

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

[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 ±1, Math. Comp. 29 (1975), no. 130, p. 620-647. | MR 384673 | Zbl 0311.10009

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

[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 1840385 | Zbl 1044.03503

[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 1445657 | Zbl 0941.11051

[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 2093202 | Zbl 1122.68456

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

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

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

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

[28] D. A. Cox - Primes of the form x 2 +ny 2 , John Wiley & Sons, 1989. | MR 1028322 | Zbl 0701.11001

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

[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 1486831 | Zbl 0915.11036

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

[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 2137354 | Zbl 1125.11359

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

[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 1850614 | Zbl 1011.11041

[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 244176 | Zbl 0201.05301

[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 1812127

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

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

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

[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 633878 | Zbl 1170.68411

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

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

[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 0900.68250

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

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

[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 647500 | Zbl 0476.10005

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

[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 685308 | Zbl 0501.10006

[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 812498 | Zbl 0561.00005

[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 934218 | Zbl 0686.14039

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

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

[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 480296 | Zbl 0365.68052

[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. | Numdam | MR 1413579 | Zbl 0843.11030

[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 1127.11084

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

[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 700254 | MR 700260 | Zbl 0508.10004

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

[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 572872 | Zbl 0444.10007

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

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

[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 1377060 | Zbl 0856.11001

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

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

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

[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 1489242

[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 429721 | Zbl 0345.10002

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

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

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

[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 1314885 | Zbl 0847.11002