Finding Smooth Integers in Short Intervals Using CRT Decoding

摘要

We present a new algorithm for CRT list decoding. An instance of the, CRT list decoding problem consists of integers B, 〈p1,…,pn〉 and 〈r1,…,rn〉, where p1n/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.