Finding smooth integers in short intervals using CRT decoding

Authors: D. Boneh

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.

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 ]