International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

An Algorithm for Finding Small Roots of Multivariate Polynomials over the Integers

Authors:
Domingo Gomez
Jaime Gutierrez
Alvar Ibeas
Download:
URL: http://eprint.iacr.org/2007/088
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2007-13370,
  title={An  Algorithm for Finding  Small Roots of Multivariate Polynomials over the Integers},
  booktitle={IACR Eprint archive},
  keywords={foundations / Lattices reduction, Factoring},
  url={http://eprint.iacr.org/2007/088},
  note={ jaime.gutierrez@unican.es 13580 received 8 Mar 2007},
  author={Domingo Gomez and Jaime Gutierrez and Alvar Ibeas},
  year=2007
}