Finding Smooth Integers in Short Intervals Using CRT Decoding
✍ Scribed by Dan Boneh
- Publisher
- Elsevier Science
- Year
- 2002
- Tongue
- English
- Weight
- 152 KB
- Volume
- 64
- Category
- Article
- ISSN
- 0022-0000
No coin nor oath required. For personal study only.
✦ Synopsis
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 -kn log p n log p 1 (approximately). The improvement is significant when k is relatively close to n, e.g. k > 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 used within the quadratic sieve factoring method.