Can I read Finding Smooth Integers in Short Intervals Using CRT Decoding on EtoBox?

Finding Smooth Integers in Short Intervals Using CRT Decoding by Dan Boneh is a Computer Science article available to read on EtoBox.

What is Finding Smooth Integers in Short Intervals Using CRT Decoding about?

We present a new algorithm for CRT list decoding. An instance of the, CRT list decoding problem consists of integers B, Op 1 , ..., p n P and Or 1 , ..., r n P, where p 1 < p 2 < ••• < p n is a sequence of relatively prime integers. The CRT list decoding problem is to find all positive integers x < B such that x=r i mod p i for all but e values of i ¥ {1, ..., n}. Suppose B=< r i=1 p i for some integer k. Goldreich, Ron, and Sudan (in ''Proc. of STOC'99'', pp. 225-234, 1999) recently gave several applications for this problem and presented the first efficient algorithm that works whenever e (approximately) satisfies e < n -`2kn log p n log p 1 . Our new algorithm achieves the stronger bound e n/3. The bounds we obtain are similar to the bounds obtained by Guruswami and Sudan for Reed-Solomon list decoding. Hence, our algorithm reduces the gap between CRT list decoding and list decoding of Reed-Solomon codes. In addition, we give a new application for CRT list decoding: finding smooth integers in short intervals. Problems of this type come up in several algorithms for factoring large integers. We define and solve a generalized CRT list decoding problem and discuss how it might be

Who reads Finding Smooth Integers in Short Intervals Using CRT Decoding?

Author

Dan Boneh

Publisher

Elsevier Science; Elsevier ; Elsevier Inc.; Elsevier BV (ISSN 0022-0000)

Published

2002

Language

EN

Field

Computer Science (Physical Sciences)