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 multiplications modulo *p*.

**[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)**

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