Small solutions to polynomial equations, and low exponent RSA vulnerabilities
type: Item
instance of: scholarly article
title: Small solutions to polynomial equations, and low exponent RSA vulnerabilities
zbMATH Open document ID: 0912.11056
author: Don Coppersmith
published in: Journal of Cryptology
publication date: 1999-05-16T00:00:00Z
review text: The problem of computing integer roots of a polynomial nicely illustrates how a seemingly small change in the problem definition may affect complexity of computing its solution. While computing integer roots of a polynomial in a single variable over the integers is easy, in the case of a modular polynomial or polynomial in several variables, finding integer roots seems to be hard. However, by imposing additional restrictions, one can specify subclasses of instances that can be efficiently solved. The paper is about solving special cases of these problems, namely those that are restricted to the case where there exists a solution small enough. The technique used here is based on using coefficients of the polynomial to build a matrix whose rows give the basis of an integer lattice. Then lattice basis reduction techniques are used to find a hyperplane containing all the short lattice elements; its equation translates into equations that can be solved to obtain a solution of the original polynomial. These results have interesting applications in cryptanalysis of RSA encryption with small exponent or factoring an integer, in both cases given some partial information on the result. As lattice basis reduction plays a central role in the approach to solving such restricted instances, after the introduction the article begins with recalling the necessary facts about lattice basis reduction. Then, a heuristic approach to solving a modular polynomial equation by lattice basis reduction techniques is given to introduce some ideas used later on. The next three sections refine the approach and show how to make the heuristic approach work. It is proved that given a polynomial of degree \(\delta\) in one variable modulo an integer \(N\) of unknown factorization, if the desired solution is bounded above by \(\frac{1}{2} N^{1/{\delta} - \epsilon}\) then the approach described allows one to find in polynomial time all integer solutions that are less then a given upper bound. In the ne…
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 11Y05
zbMATH DE Number: 1133022
zbMATH Keywords: polynomials
zbMATH Keywords: integer roots
zbMATH Keywords: lattice basis reduction
zbMATH Keywords: RSA
zbMATH Keywords: factoring
zbMATH Keywords: modular polynomial equation
zbMATH Keywords: small solutions
Wikidata QID: Q54136651
reviewed by: Jozef Vyskoč
MaRDI profile type: Publication
full work available at URL: s001459900030
OpenAlex ID: W2101040389
DOI: 10.1007/S001459900030
description: scientific article; zbMATH DE number 1133022