Finding smooth integers in short intervals using CRT decoding
Authors: D. Boneh
Abstract:
We present a new algorithm for CRT list decoding. Given B,
< p_1,...,p_n> and < r_1,...,r_n>, where the
p_i's are relatively prime, the CRT list decoding problem asks for
all positive integers x < B such that x = r_i mod p_i for all but
e values of i in {1,...,n}. Suppose B = \prod_{i=1}^k p_i
for some integer k. Goldreich, Ron, and Sudan recently gave several
applications for this problem and presented the first efficient algorithm
whenever e (approximately) satisfies e < n-\sqrt{2kn{\log p_n \over \log
p_1}}. Our new algorithm achieves the stronger bound e <
n-\sqrt{kn{\log p_n \over \log p_1}}. The improvement is significant when
k is relatively close to n, e.g. k>n/3. Our algorithm bridges
the gap between CRT list decoding and the dual problem of list decoding
Reed-Solomon codes. The bounds we obtain are identical to the bounds
obtained by Guruswami and Sudan for Reed-Solomon list decoding. In
addition, we give a new application for CRT list decoding: finding smooth
integers in short intervals. This problem is relevant to factoring
large integers. We define and solve a generalized CRT list decoding
problem and show how it can be used within the quadratic sieve factoring
method.
Reference:
Journal of Computer and System Sciences (JCSS), Vol. 64, pp. 768--784, 2002
Extended abstract in STOC '2000, pp. 265--272, Portland, Oregon, 2000
Full paper: PostScript [first posted 10/2001 ]