Very short primality proofs
HTML articles powered by AMS MathViewer
- by Carl Pomerance PDF
- Math. Comp. 48 (1987), 315-322 Request permission
Abstract:
It is shown that every prime p has a proof of its primality of length $O(\log p)$ multiplications modulo p.References
- Eric Bach, Analytic methods in the analysis and design of number-theoretic algorithms, ACM Distinguished Dissertations, MIT Press, Cambridge, MA, 1985. MR 807772 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.
- Max Deuring, Die Typen der Multiplikatorenringe elliptischer Funktionenkörper, Abh. Math. Sem. Hansischen Univ. 14 (1941), 197–272 (German). MR 5125, DOI 10.1007/BF02940746 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. H. W. Lenstra, Jr., "Factoring integers with elliptic curves." (To appear).
- Gary L. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), no. 3, 300–317. MR 480295, DOI 10.1016/S0022-0000(76)80043-8
- Peter L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), no. 177, 243–264. MR 866113, DOI 10.1090/S0025-5718-1987-0866113-7
- Vaughan R. Pratt, Every prime has a succinct certificate, SIAM J. Comput. 4 (1975), no. 3, 214–220. MR 391574, DOI 10.1137/0204018 A. Schönhage, "Schnelle Berechnung von Kettenbruchentwicklungen," Acta Inform., v. 1, 1971, pp. 139-144. R. J. Schoof, "Nonsingular plane cubic curves over finite fields," J. Combin. Theory. (To appear).
- Daniel Shanks, Solved and unsolved problems in number theory, 3rd ed., Chelsea Publishing Co., New York, 1985. MR 798284
- John T. Tate, The arithmetic of elliptic curves, Invent. Math. 23 (1974), 179–206. MR 419359, DOI 10.1007/BF01389745
- William C. Waterhouse, Abelian varieties over finite fields, Ann. Sci. École Norm. Sup. (4) 2 (1969), 521–560. MR 265369
- Andrew Chi Chih Yao, On the evaluation of powers, SIAM J. Comput. 5 (1976), no. 1, 100–103. MR 395331, DOI 10.1137/0205008
Additional Information
- © Copyright 1987 American Mathematical Society
- 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