Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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

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.


References [Enhancements On Off] (What's this?)

  • [1] E. Bach, Analytic Methods in the Analysis and Design of Number-Theoretic Algorithms, MIT Press, Cambridge, Mass., 1985. MR 807772 (87i:11185)
  • [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] M. Deuring, "Die Typen der Multiplikatorenringe elliptischer Funktionenkörper," Abh. Math. Sem. Univ. Hamburg, v. 14, 1941, pp. 197-272. MR 0005125 (3:104f)
  • [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] G. L. Miller, "Riemann's hypothesis and tests for primality," J. Comput. System Sci., v. 13, 1976, pp. 300-317. MR 0480295 (58:470a)
  • [7] P. L. Montgomery, "Speeding the Pollard and elliptic curve methods of factorization," Math. Comp., v. 48, 1987, pp. 243-264. MR 866113 (88e:11130)
  • [8] V. R. Pratt, "Every prime has a succinct certificate," SIAM J. Comput., v. 4, 1975, pp. 214-220. MR 0391574 (52:12395)
  • [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] D. Shanks, Solved and Unsolved Problems in Number Theory, 3rd ed., Chelsea, New York, 1985. MR 798284 (86j:11001)
  • [12] J. T. Tate, "The arithmetic of elliptic curves," Invent. Math., v. 23, 1974, pp. 179-206. MR 0419359 (54:7380)
  • [13] W. C. Waterhouse, "Abelian varieties over finite fields," Ann. Sci. École Norm. Sup., v. 2, 1969, pp. 521-560. MR 0265369 (42:279)
  • [14] A. C. Yao, "On the evaluation of powers," SIAM J. Comput., v. 5, 1976, pp. 100-103. MR 0395331 (52:16128)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y11, 11Y16

Retrieve articles in all journals with MSC: 11Y11, 11Y16


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1987-0866117-4
Article copyright: © Copyright 1987 American Mathematical Society

American Mathematical Society