Efficient Interpolation in the Guruswami–-Sudan Algorithm

A novel algorithm is proposed for the interpolation step of the Guruswami-Sudan list decoding algorithm. The proposed method is based on the binary exponentiation algorithm, and can be considered as an extension of the Lee-O'Sullivan method. The algorithm is shown to achieve both asymptotical and practical performance gain compared to the case of iterative interpolation algorithm. Further complexity reduction is achieved by employing the reencoding transformation. The key contribution of the paper, which enables the complexity reduction, is a novel randomized ideal multiplication algorithm.