Paper 2007/088

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

Domingo Gomez, 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Lattices reductionFactoring
Contact author(s)
jaime gutierrez @ unican es
History
2007-03-08: received
Short URL
https://ia.cr/2007/088
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/088,
      author = {Domingo Gomez and Jaime Gutierrez and Alvar Ibeas},
      title = {An  Algorithm for Finding  Small Roots of Multivariate Polynomials over the Integers},
      howpublished = {Cryptology ePrint Archive, Paper 2007/088},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/088}},
      url = {https://eprint.iacr.org/2007/088}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.