Finding smooth integers in short intervals using CRT decoding
Dan Boneh · 2000
We present a new algorithm for CRT list decoding.Given B,(pl,... ,p~) and (rl,... ,r,~), where the pi's are relatively prime, the CRT list decoding problem asks for all positive integers x n/3.The bounds we obtain are identical to the bounds obtained by Guruswami and Sudan for Reed-Solomon list decoding.Hence, our algorithm closes 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.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.