Cryptology ePrint Archive: Report 2007/088
An Algorithm for Finding Small Roots of Multivariate Polynomials over the Integers
Domingo Gomez and Jaime Gutierrez and Alvar Ibeas
Abstract: In this paper we present a new algorithm for finding small roots of a system of multivariate polynomials over the integers based on lattice reduction techniques. Our simpler heuristic
method is inspired in algorithms for predicting pseudorandom numbers, and it can be considered as another variant of Coppersmith's method for finding small solutions of integer bivariate polynomials.
We also apply the method to the well known problem of factoring an integer when we know the high-order bits of one of the factors.
Category / Keywords: foundations / Lattices reduction, Factoring
Date: received 8 Mar 2007
Contact author: jaime gutierrez at unican es
Available format(s): PDF | BibTeX Citation
Version: 20070308:140404 (All versions of this report)
Short URL: ia.cr/2007/088
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]