A Variant of Coppersmith's Algorithm with Improved Complexity and Efficient Exhaustive Search.

摘要: Coppersmith described at Eurocrypt 96 a polynomial-time algorithm for finding small roots of univariate modular equations, based on lattice reduction. In this paper we describe the first improvement asymptotic complexity Coppersmith’s algorithm. Our method consists in taking advantage matrix structure, order to apply LLL whose elements are smaller than those original matrix. Using L algorithm, our is O(logN) any e > 0, instead previously. Furthermore, devise that allows speed up exhaustive search which usually performed reach theoretical bound. approach takes test one guess, reduce next guess. Experimental results confirm it leads considerable performance improvement.