The number field sieve

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The number field sieve

Full text

Pdf (880 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-second annual ACM symposium on Theory of computing table of contents

Baltimore, Maryland, United States

Pages: 564 - 572

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

A. K. Lenstra	Department of Mathematics, University of California, Berkeley, CA
H. W. Lenstra, Jr.
M. S. Manasse	DEC SRC, 130 Lytton Avenue, Palo Alto, CA
J. M. Pollard	Tidmarsh Cottage, Manor Farm Lane, Tidmarsh, Reading, Berkshire. RG8 SEX, United Kingdom

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 43, Citation Count: 12

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/100216.100295 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.

	1	1 Red Alford, C. Pomerance, personal communication.
	2	2 J. Brillhart, D.H. Lehmer, J.L. Selfridge, B. Tuckerman, S.S. Wagstaff, Jr., Factorizations of bⁿ±1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers, second edition, Contemporary Mathematics, vol. 22, Providence: A.M.S., 1988.
	3	3 J. Buhler, H.W. Lenstra, Jr., C. Pomerance, in preparation.
	4	4 T.R. Caron, R.D. Silverman, "Parallel implementation of the quadratic sieve," J. Supercomputing, v. 1, 1988, pp. 273-290.
	5	Don Coppersmith , Andrew M. Odlyzko , Richard Schroeppel, Discrete logarithms in GF(p), Algorithmica, v.1 n.1, p.1-15, Jan. 1986 [doi>10.1007/BF01840433]
	6	6 D.E. Knuth, "Computer Science and its relation to mathematics," Amer. Math. Monthly, v. 81, 1974, pp. 323-342.
	7	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	8	8 S. Lang, Algebra, second edition, Addison-Wesley, Reading, 1984.
	9	A. K. Lenstra , H. W. Lenstra, Jr., Algorithms in number theory, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	10	Arjen K. Lenstra , Mark S. Manasse, Factoring by electronic mail, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.355-371, November 1990, Houthalen, Belgium
	11	11 M.A. Morrison, J. Brillhart, "A method of factoring and the factorization of F7," Math. Comp., v. 29, 1975, pp. 183-205.
	12	12 C. Pomerance, "Analysis and comparison of some integer factoring algorithms," pp. 89-139 in: H.W. Lenstra, Jr., R. Tijdeman (eds), Computational methods in number theory, Math. Centre Tracts 154/155, Mathematisch Centrum, Amsterdam 1982.
	13	13 C. Pomerance, S.S. Wagstaff, Jr., "Implementation of the continued fraction integer factoring algorithm," Congress. Numer., v. 37, 1983, pp. 99-118.
	14	14 H.J.J. te Riele, W.M. Lioen, D.T. Winter, "Factoring with the quadratic sieve on large vector computers," report NM-R8805, 1988, Centrum voor Wiskunde en Informatica, Amsterdam.
	15	15 I.N. Stewart, D.O. Tall, Algebraic number theory, second edition, Chapman and Hall, 1987.
	16	D H Wiedemann, Solving sparse linear equations over finite fields, IEEE Transactions on Information Theory, v.32 n.1, p.54-62, Jan. 1986 [doi>10.1109/TIT.1986.1057137]

CITED BY 12

	James Goodman , Anantha P. Chandrakasan, Low power scalable encryption for wireless systems, Wireless Networks, v.4 n.1, p.55-70, Jan. 1998
	Leonard M. Adleman, Factoring numbers using singular integers, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.64-71, May 05-08, 1991, New Orleans, Louisiana, United States
	Hea Joung Kim , William H. Mangione-Smith, Factoring large numbers with programmable hardware, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.41-48, February 10-11, 2000, Monterey, California, United States
	David H. Bailey, Algorithm 719; Multiprecision translation and execution of FORTRAN programs, ACM Transactions on Mathematical Software (TOMS), v.19 n.3, p.288-319, Sept. 1993
	Joachim von zur Gathen, A polynomial factorization challenge, ACM SIGSAM Bulletin, v.26 n.2, p.22-24, April 1992
	Mihai Udrescu , Lucian Prodan , Mircea Vlǎdutiu, Using HDLs for describing quantum circuits: a framework for efficient quantum algorithm simulation, Proceedings of the 1st conference on Computing frontiers, April 14-16, 2004, Ischia, Italy
	Ueli M. Maurer , Yacov Yacobi, A Non-interactive Public-Key Distribution System, Designs, Codes and Cryptography, v.9 n.3, p.305-316, Nov. 1996
	Rob H. Bisseling , Ildikó Flesch, Mondriaan sparse matrix partitioning for attacking cryptosystems by a parallel block Lanczos algorithm: a case study, Parallel Computing, v.32 n.7, p.551-567, September 2006
	Markus Hunziker , David A. Meyer, Quantum Algorithms for Highly Structured Search Problems, Quantum Information Processing, v.1 n.3, p.145-154, June 2002
	Anne Broadbent , Alain Tapp, Can quantum mechanics help distributed computing?, ACM SIGACT News, v.39 n.3, September 2008
	Yossef Oren , Martin Feldhofer, A low-resource public-key identification scheme for RFID tags and sensor nodes, Proceedings of the second ACM conference on Wireless network security, March 16-19, 2009, Zurich, Switzerland
	Shunichi Hayashi , Mitsuru Tada, New NP-Complete Problems Associated with Lattices, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E90-A n.5, p.941-948, May 2007