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]**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**0005125****[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. Working papers presented at the ACM-SIGACT Symposium on the Theory of Computing (Albuquerque, N.M., 1975). MR**0480295**, 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**0391574**, 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**0419359**, 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**0265369****[14]**Andrew Chi Chih Yao,*On the evaluation of powers*, SIAM J. Comput.**5**(1976), no. 1, 100–103. MR**0395331**, https://doi.org/10.1137/0205008

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