International Association for Cryptologic Research

2003 IACR Distinguished Lecture


Don Coppersmith

Solving Low Degree Polynomials

presented at ASIACRYPT 2003, in Taipei, Taiwan.

Abstract

Given an integer N, and a polynomial p(x) of degree d in one
variable, defined modulo N, and the bound $B=N^{1/d}$, we
can efficiently find all integer solutions $x_0$ with 
$|x_0| < B$ and $p(x_0)=0 mod B$.  This has applications to
low-exponent RSA encryption.  

Based on work in Eurocrypt 1996.
The slides from the lecture are available: