2003 IACR Distinguished Lecture
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: