Primality in polynomial time

 Access to full text

 Full (PDF)

1. [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. Zbl0526.10004
2. [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. Zbl0744.11065MR1176511
3. [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. Zbl0526.10004MR683806
4. [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. Zbl0368.94005MR700103
5. [5] M. Agrawal & S. Biswas – “Primality and identity testing via chinese remaindering”, in Proc. Ann. IEEE Symp. Found. Comp. Sci., 1999, p. 202–209. MR1917560
6. [6] M. Agrawal, N. Kayal & N. Saxena – “PRIMES is in P”, Preprint ; available at http://www.cse.iitk.ac.in/primality.pdf, 2002. Zbl1071.11070MR2123939
7. [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. Zbl0816.11005MR1283874
8. [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. MR213289
9. [9] A.O.L. Atkin & F. Morain – “Elliptic curves and primality proving”, Math. Comp. 61 (1993), no. 203, p. 29–68. Zbl0792.11056MR1199989
10. [10] E. Bach – “Explicit bounds for primality testing and related problems”, Math. Comp. 55 (1990), no. 191, p. 355–380. Zbl0701.11075MR1023756
11. [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. Zbl0853.11078MR1399332
12. [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. Zbl1016.11037MR1851081
13. [13] D. Bernstein – “An exposition of the Agrawal-Kayal-Saxena primality-proving theorem”, Preprint, 2002. 
14. [14] —, “Proving primality after Agrawal-Kayal-Saxena”, http://cr.yp.to/papers/aks.ps, 2003. 
15. [15] —, “Proving primality in essentially quartic expected time”, http://cr.yp.to/papers/quartic.ps, 2003. 
16. [16] P. Berrizbeitia – “Sharpening “Primes is in P” for a large family of numbers”, http://arxiv.org/abs/math.NT/0211334, 2002. Zbl1071.11071MR2164112
17. [17] I. Blake, G. Seroussi & N. Smart – Elliptic curves in cryptography, London Math. Soc. Lecture Note Ser., vol. 265, Cambridge University Press, 1999. Zbl0937.94008MR1771549
18. [18] W. Bosma & M.-P. van der Hulst – “Primality proving with cyclotomy”, Thèse, Universiteit van Amsterdam, 1990. 
19. [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. Zbl0311.10009MR384673
20. [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. Zbl0659.10001
21. [21] O. Caprotti & M. Oostdijk – “Formal and efficient primality proofs by use of computer algebra oracles”, J. Symbolic Comput.32 (2001), p. 55–70. Zbl1044.03503MR1840385
22. [22] H.F. Chau & H.-K. Lo – “Primality test via quantum factorization”, Internat. J. Modern Phys. C 8 (1997), no. 2, p. 131–138. Zbl0941.11051MR1445657
23. [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. Zbl1122.68456MR2093202
24. [24] H. Cohen – A course in algorithmic algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer–Verlag, 1996, Third printing. Zbl0786.11071
25. [25] H. Cohen & A.K. Lenstra – “Implementation of a new primality test”, Math. Comp. 48 (1987), no. 177, p. 103–121. Zbl0608.10001MR866102
26. [26] H. Cohen & H.W. Lenstra, Jr. – “Primality testing and Jacobi sums”, Math. Comp. 42 (1984), no. 165, p. 297–330. Zbl0578.10004MR726006
27. [27] L. Comtet – Analyse combinatoire, Presses Universitaires de France, 1970. Zbl0221.05002MR262087
28. [28] D.A. Cox – Primes of the form $x^2+n{y}^2$, John Wiley & Sons, 1989. Zbl0701.11001MR1028322
29. [29] R. Crandall & C. Pomerance – Prime numbers – a computational perspective, Springer Verlag, 2000. Zbl1088.11001MR2156291
30. [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. Zbl0915.11036MR1486831
31. [31] E. Fouvry – “Théorème de Brun-Titschmarsh ; application au théorème de Fermat”, Invent. Math.79 (1985), p. 383–407. Zbl0557.10035MR778134
32. [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. Zbl1125.11359MR2137354
33. [33] J. von zur Gathen & J. Gerhard – Modern computer algebra, Cambridge University Press, 1999. Zbl1055.68168MR1689167
34. [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. Zbl1011.11041MR1850614
35. [35] M. Goldfeld – “On the number of primes $p$ for which $p+a$ has a large prime factor”, Mathematika16 (1969), p. 23–27. Zbl0201.05301MR244176
36. [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. [37] —, “Primality testing using elliptic curves”, Journal of the ACM 46 (1999), no. 4, p. 450–472. Zbl1064.11503MR1812127
38. [38] D.R. Heath-Brown – “The differences between consecutive primes”, J. London Math. Soc. (2) 18 (1978), no. 1, p. 7–13. Zbl0387.10025MR491554
39. [39] K. Ireland & M. Rosen – A classical introduction to modern number theory, Graduate Texts in Mathematics, vol. 84, Springer, 1982. Zbl0482.10001MR661047
40. [40] H. Iwaniec & M. Jutila – “Primes in short intervals”, Ark. Mat. 17 (1979), no. 1, p. 167–176. Zbl0408.10029MR543511
41. [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. [42] D.E. Knuth – The Art of Computer Programming : Seminumerical algorithms, 2nd ’ed., Addison-Wesley, 1981. Zbl1170.68411MR633878
43. [43] H. Lange & W. Ruppert – “Complete systems of addition laws on abelian variety”, Invent. Math.79 (1985), p. 603–610. Zbl0577.14035MR782238
44. [44] D.H. Lehmer – “Strong Carmichael numbers”, J. Austral. Math. Soc. Ser. A21 (1976), p. 508–510. Zbl0327.10011MR417032
45. [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. Zbl0900.68250
46. [46] —(éds.) – The development of the number field sieve, Lecture Notes in Math., vol. 1554, Springer, 1993. Zbl0806.11066MR1321216
47. [47] H.W. Lenstra, Jr. – “Miller’s primality test”, Inform. Process. Lett. 8 (1979), no. 2, p. 86–88. Zbl0399.10006MR520273
48. [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. Zbl0476.10005MR647500
49. [49] —, “Primality testing”, in Computational methods in number theory, Part I, Math. Centrum, Amsterdam, 1982, p. 55–77. Zbl0507.10003MR700258
50. [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. Zbl0501.10006MR685308
51. [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. Zbl0561.00005MR812498
52. [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. Zbl0686.14039MR934218
53. [53] —, “Factoring integers with elliptic curves”, Ann. of Math. (2) 126 (1987), p. 649–673. Zbl0629.10006MR916721
54. [54] A. Menezes, P.C. van Oorschot & S.A. Vanstone – Handbook of applied cryptography, CRC Press, 1997. Zbl0868.94001MR1412797
55. [55] P. Mihăilescu – “Cyclotomy of rings and primality testing”, Diss. ETH No. 12278, Swiss Federal Institute of Technology Zürich, 1997. 
56. [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. [57] G.L. Miller – “Riemann’s hypothesis and tests for primality”, in Proc. 7th STOC, 1975, p. 234–239. Zbl0365.68052MR480296
58. [58] F. Morain – “Calcul du nombre de points sur une courbe elliptique dans un corps fini : aspects algorithmiques”, J. Théor. Nombres Bordeaux7 (1995), p. 255–282. Zbl0843.11030MR1413579
59. [59] —, “Implementing the asymptotically fast version of the elliptic curve primality proving algorithm”, Available at http ://www.lix.polytechnique.fr/Labo/Francois.Morain/, 2003. Zbl1127.11084
60. [60] C.H. Papadimitriou – Computational complexity, Addison-Wesley, 1995. Zbl0833.68049MR1251285
61. [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. Zbl0508.10004MR700260
62. [62] —, “Very short primality proofs”, Math. Comp. 48 (1987), no. 177, p. 315–322. Zbl0608.10002MR866117
63. [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. Zbl0444.10007MR572872
64. [64] V.R. Pratt – “Every prime has a succint certificate”, SIAM J. Comput.4 (1975), p. 214–220. Zbl0316.68031MR391574
65. [65] M. Rabin – “Probabilistic algorithms for testing primality”, J. Number Theory12 (1980), p. 128–138. Zbl0426.10006MR566880
66. [66] J. Radhakrishnan – “Primes in P”, Bull. of the EATCS78 (2002), p. 61–65. 
67. [67] P. Ribenboim – The new book of prime number records, Springer-Verlag, 1996. Zbl0856.11001MR1377060
68. [68] J.B. Rosser & L. Schoenfeld – “Approximate formulas for some functions of prime numbers”, Illinois J. Math.6 (1962), p. 64–94. Zbl0122.05001MR137689
69. [69] R. Schoof – “Elliptic curves over finite fields and the computation of square roots mod $p$”, Math. Comp.44 (1985), p. 483–494. Zbl0579.14025MR777280
70. [70] —, “Counting points on elliptic curves over finite fields”, J. Théor. Nombres Bordeaux7 (1995), p. 219–254. Zbl0852.11073MR1413578
71. [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. MR1489242
72. [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. Zbl0345.10002MR429721
73. [73] P. van Wamelen – “Jacobi sums over finite fields”, Acta Arith. 102.1 (2002), p. 1–20. Zbl1047.11116MR1884953
74. [74] E. Waterhouse – “Abelian varieties over finite fields”, Ann. Sci. École Norm. Sup.2 (1969), p. 521–560. Zbl0188.53001MR265369
75. [75] A. Weng – “Constructing hyperelliptic curves of genus 2 suitable for cryptography”, Math. Comp.72 (2003), p. 435–458. Zbl1013.11023MR1933830
76. [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. Zbl0847.11002MR1314885