Very short primality proofs

Pomerance, Carl

doi:10.1090/S0025-5718-1987-0866117-4

Very short primality proofs

Author: Carl Pomerance
Journal: Math. Comp. 48 (1987), 315-322
MSC: Primary 11Y11; Secondary 11Y16
DOI: https://doi.org/10.1090/S0025-5718-1987-0866117-4
MathSciNet review: 866117
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: It is shown that every prime p has a proof of its primality of length $O(\log p)$ multiplications modulo p.

[1] Eric Bach, Analytic methods in the analysis and design of number-theoretic algorithms, ACM Distinguished Dissertations, MIT Press, Cambridge, MA, 1985. MR 807772
[2] D. V. Chudnovsky & G. V. Chudnovsky, Sequences of Numbers Generated by Addition in Formal Groups and New Primality and Factorization Tests, Research Report RC 11262 (#50739), IBM Thomas J. Watson Research Center, Yorktown Heights, New York, 1985.
[3] Max Deuring, Die Typen der Multiplikatorenringe elliptischer Funktionenkörper, Abh. Math. Sem. Hansischen Univ. 14 (1941), 197–272 (German). MR 5125, https://doi.org/10.1007/BF02940746
[4] S. Goldwasser & J. Kilian, Almost All Primes Can Be Quickly Certified, Proc. 18th Annual ACM Sympos. on Theory of Computing (STOC), Berkeley, May 28-30, 1986, pp. 316-329.
[5] H. W. Lenstra, Jr., "Factoring integers with elliptic curves." (To appear).
[6] Gary L. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), no. 3, 300–317. MR 480295, https://doi.org/10.1016/S0022-0000(76)80043-8
[7] Peter L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), no. 177, 243–264. MR 866113, https://doi.org/10.1090/S0025-5718-1987-0866113-7
[8] Vaughan R. Pratt, Every prime has a succinct certificate, SIAM J. Comput. 4 (1975), no. 3, 214–220. MR 391574, https://doi.org/10.1137/0204018
[9] A. Schönhage, "Schnelle Berechnung von Kettenbruchentwicklungen," Acta Inform., v. 1, 1971, pp. 139-144.
[10] R. J. Schoof, "Nonsingular plane cubic curves over finite fields," J. Combin. Theory. (To appear).
[11] Daniel Shanks, Solved and unsolved problems in number theory, 3rd ed., Chelsea Publishing Co., New York, 1985. MR 798284
[12] John T. Tate, The arithmetic of elliptic curves, Invent. Math. 23 (1974), 179–206. MR 419359, https://doi.org/10.1007/BF01389745
[13] William C. Waterhouse, Abelian varieties over finite fields, Ann. Sci. École Norm. Sup. (4) 2 (1969), 521–560. MR 265369
[14] Andrew Chi Chih Yao, On the evaluation of powers, SIAM J. Comput. 5 (1976), no. 1, 100–103. MR 395331, https://doi.org/10.1137/0205008