Almost all primes can be quickly certified

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Almost all primes can be quickly certified

Full text

Pdf (1.01 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the eighteenth annual ACM symposium on Theory of computing table of contents

Berkeley, California, United States

Pages: 316 - 329

Year of Publication: 1986

ISBN:0-89791-193-8

Authors

S Goldwasser	EECS Department and Laboratory for Computer Science, Massachusetts Institute of Technology
J Kilian	Department of Mathematics and Laboratory for Computer Science, Massachusetts Institute of Technology

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 50, Citation Count: 14

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/12130.12162 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	APR	Adleman, Pomerance, Rumely, "On Distinguishing prime numbers from composite numbers",to appear. Ext. Abstract 21st FOCS (1980), 387-406.
	BLS	Brillhart, Lehmer, Selfridge, "New Primality7 Criteria and Factorization of 2sup m+i", vol 29, no. 1930 (1975).
	Ba2	Bach Eric, "Lenstra's Algorithm for Factoring with Elliptic Curves (Expose)", notes, February 27th, 1985.
	CL	Choen, Lenstra, "Primality Testing and Jacobi Sums", to appear.
	D	Dickson, " History of the Theory of Numbers", Chelsea Publishing Company, 1952.
	F	Martin Fürer, Deterministic and Las Vegas Primality Testing Algorithms, Proceedings of the 12th Colloquium on Automata, Languages and Programming, p.199-209, July 15-19, 1985
	lIB	Heath- Brown D. R., "The Differences between Consecutive Primes", J. London Math. Soc. (2), 18 (1978), 7-13.
	L	Lenstra, "Factoring Integers using Elliptic Curves over Finite Fields", to appear.
	M	Miller, "Riemann Hypothesis and test for primality", JCSS 13 (1976), 300-317.
	MP	Maier H., Pomerance C., Personnal Communication.
	P	Plaisted, "Generating Large Prime Numbers".
	P	Pratt, "Every Prime has a Succinct Certificate", SIAM J. of Comp. (1975), 214-220.
	R	Rabin, "Probabilistic Algorithms for Testing Primality", J. of Num. Th. 12, 128-138 (1980).
	Sch	School, "Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p", Math. Computation, Vol. 44, Num 170, April 1985, pp.
	Sh	Shallit, "Lenstra's Elliptic Curve Factoring Algorithm", notes, March 15, 1985.
	Se	Selberg, "On the Normal Density of Primes in Small Intervals, and the Difference between Consecutive Primes", Archly for Mathematik of Naturvidensakb B. XLVII. Nr. 6. 483-494.
	Sha	Shanks, "On Maximal Gaps between Successive Primes", Math. Computation, Vol. 18, pp. 646-651, 1964.
	SS	Solovay and Strassen, "A fast Monte-Carlo test for Primality", SIAM. J. of Comp. 6 (1977), 84-85.
	T	Tate, "The Arithmetic of Elliptic Curves", Inventiones Math. 23, (1974), 179-206.

CITED BY 14

	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	Shafi Goldwasser , Joe Kilian, Primality testing using elliptic curves, Journal of the ACM (JACM), v.46 n.4, p.450-472, July 1999
	E. Allender, Some consequences of the existence of pseudorandom generators, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.151-159, January 1987, New York, New York, United States
	Cynthia Dwork , Larry Stockmeyer, 2-round zero knowledge and proof auditors, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	F. Morain, Easy numbers for the elliptic curve primality proving algorithm, Papers from the international symposium on Symbolic and algebraic computation, p.263-268, July 27-29, 1992, Berkeley, California, United States
	L. Adleman , M. Huang, Recognizing primes in random polynomial time, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.462-469, January 1987, New York, New York, United States
	Richard Cole , Ramesh Hariharan, Verifying candidate matches in sparse and wildcard matching, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	János Pintz , William Steiger , Endre Szemerédi, Two infinite sets of primes with fast primality tests, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.504-509, May 02-04, 1988, Chicago, Illinois, United States
	E. Bach, Realistic analysis of some randomized algorithms, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.453-461, January 1987, New York, New York, United States
	Keju Ma , Joachim von zur Gathen, The computational complexity of recognizing permutation functions, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.392-401, May 23-25, 1994, Montreal, Quebec, Canada
	E. Kaltofen , T. Valente , N. Yui, An improved Las Vegas primality test, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.26-33, July 17-19, 1989, Portland, Oregon, United States
	David S. Johnson, The NP-completeness column, ACM Transactions on Algorithms (TALG), v.1 n.1, p.160-176, July 2005
	Ueli M. Maurer , Stefan Wolf, The Diffie–Hellman Protocol, Designs, Codes and Cryptography, v.19 n.2-3, p.147-171, March 2000
	Neal Koblitz , Alfred Menezes , Scott Vanstone, The State of Elliptic Curve Cryptography, Designs, Codes and Cryptography, v.19 n.2-3, p.173-193, March 2000