Finding smooth integers in short intervals using CRT decoding

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Finding smooth integers in short intervals using CRT decoding

Full text

Pdf (712 KB)

Source

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

Portland, Oregon, United States

Pages: 265 - 272

Year of Publication: 2000

ISBN:1-58113-184-4

Author

Dan Boneh

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): 21, Citation Count: 5

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/335305.335337 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	Sigal Ar , Richard J. Lipton , Ronitt Rubinfeld , Madhu Sudan, Reconstructing Algebraic Functions from Mixed Data, SIAM Journal on Computing, v.28 n.2, p.487-510, April 1999 [doi>10.1137/S0097539796297577]
	2	D. Bleichenbacher, P. Nguyen, "Noisy Polynomial Interpolation and Noisy Chinese Remaindering", to appear in Eurocrypt '2000.
	3	D. Boneh, G. Durfee, "Cryptanalysis of RSA with private key d ~ N~'~'92'', Proc. of Eurocrypt '98, pp. 1-11, 1998.
	4	Dan Boneh , Glenn Durfee , Nick Howgrave-Graham, Factoring N = prq for Large r, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.326-337, August 15-19, 1999
	5	D. Coppersmith, "Small solutions to polynomial equations, and low exponent RSA vulnerabilities", J. of Cryptology, Vol. 10, pp. 233-260, 1997.
	6	Oded Goldreich , Dana Ron , Madhu Sudan, Chinese remaindering with errors, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.225-234, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301309]
	7	O. Goldreich , R. Rubinfeld , M. Sudan, Learning polynomials with queries: The highly noisy case, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.294, October 23-25, 1995
	8	V. Guruswami, M. Sudan, "improved decoding for Reed-Solomon and algebraic geometric codes", IEEE Tran. on Info. Theory, vol. 45, no. 6, pp 1757- 1767, 1999.
	9	Nick Howgrave-Graham, Finding Small Roots of Univariate Modular Equations Revisited, Proceedings of the 6th IMA International Conference on Cryptography and Coding, p.131-142, December 17-19, 1997
	10	R. Kotter, "A unified description of an error locating procedure for linear codes", in proc. of Algebraic and Combinatorial Coding Theory, 1992.
	11	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
	12	A. Lenstra, H.W. Lenstra Jr., "The development of the number field sieve", Lecture Notes in Mathematics, Vol. 1554, Springer-Verlag, 1994.
	13	A. Lenstra, H.W. Lenstra Jr., and L. Lovasz, "Factoring polynomial with rational coefficients", Mathematiche Annalen, 261:515-534, 1982.
	14	L. Lovasz, "An algorithmic theory of numbers, graphs and convexity", SIAM lecture series, Vol. 50, 1986.
	15	D. Mandelbaum, "On a class of arithmetic codes and a decoding algorithm", IEEE Tran. on Info. theory, vol. 22, No. 1, pp. 85-88, 1976.
	16	D. Mandelbaum, "Further results on decoding arithmetic residue codes", IEEE Tran. on Info. theory, vol. 24, No. 5, pp. 643-644, 1978.
	17	Moni Naor , Benny Pinkas, Oblivious transfer and polynomial evaluation, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.245-254, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301312]
	18	Michael A Soderstrand , W Kenneth Jenkins , Graham A Jullien , Fred J Taylor, Residue number system arithmetic: modern applications in digital signal processing, IEEE Press, Piscataway, NJ, 1986
	19	Madhu Sudan, Decoding of Reed Solomon codes beyond the error-correction bound, Journal of Complexity, v.13 n.1, p.180-193, March 1997 [doi>10.1006/jcom.1997.0439]

CITED BY 5

	Amnon Ta-Shma , David Zucherman, Extractor codes, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.193-199, July 2001, Hersonissos, Greece
	Dan Boneh, Finding smooth integers in short intervals using CRT decoding, Journal of Computer and System Sciences, v.64 n.4, p.768-784, June 2002
	Johan Håstad , Mats Nåslund, The security of all RSA and discrete log bits, Journal of the ACM (JACM), v.51 n.2, p.187-230, March 2004
	Claus Peter Schnorr, Fast LLL-type lattice reduction, Information and Computation, v.204 n.1, p.1-25, January 2006
	Venkatesan Guruswami, Algorithmic results in list decoding, Foundations and Trends® in Theoretical Computer Science, v.2 n.2, p.107-195, January 2007