Understanding the Coppersmith's method

• Introduction
• An overview

Introduction

Before we get into the details, let us first answer three big questions: what, when, and how.

Coppersmith’s method is a technique for finding small roots of polynomial equations. More specifically, it is used to find small solutions to polynomial congruences modulo a composite integer, even when the factorisation of the modulus is unknown. Finding roots modulo a prime can often be done efficiently using methods such as Cantor–Zassenhaus or Berlekamp’s algorithm. But in the composite case, the problem becomes much harder since it is somewhat related to the factoring problem, for example in the case where $\displaystyle N=pq$ , which is hard.

Coppersmith’s method is based on lattice reduction techniques. Its main advantage is that it provides provable guarantees for finding all roots smaller than a certain bound $\displaystyle X$ in polynomial time. This bound depends on the size of the modulus and the degree of the target polynomial.

Now, let us move onto the details and work through some practical implementation.

An overview

Let $\displaystyle N$ be a composite integer and $\displaystyle f( x) =x^{d} +\sum_{i=0}^{d-1} a_{i} x^{i} \in \mathbb{Z}[ x]$ be a monic polynomial of degree $\displaystyle d$. If $\displaystyle f$ is not monic, we can multiply by the inverse of the leading coefficient $\displaystyle \bmod N$. If this inverse does not exist, then we can factor $\displaystyle N$ and proceed recursively.

Our main goal is to find all integer solutions $\displaystyle x_{0}$ to the equation $\displaystyle f( x_{0}) =0\bmod N$ which satisfy $\displaystyle |x_{0}|< B$ for some bound $\displaystyle B$ depending on $\displaystyle N$ and $\displaystyle d$.

The main idea of the algorithm is to construct a polynomial $\displaystyle g( x)$ over the integer which also satisfies $\displaystyle g( x_{0}) =0$. Since we are already know how to efficiently find roots of univariate polynomials over the integers so this should be easy.

The first approch is due to Hastad: We consider the class of polynomial of the form $\displaystyle g_{i}( x) =Nx^{i} \in \mathbb{Z}[ x]$ which have the same roots as $\displaystyle f\bmod N$. So we consider the lattice generated by the rows of $\displaystyle B$ :

The first $\displaystyle d$ rows encode the polynomials $\displaystyle g_{i}( Bx)$ for $\displaystyle 0\leqslant i< d$ and the last row encodes $\displaystyle f( Bx)$. Recall that the LLL method in fact performs integer linear combinations on the rows of our given matrix. And because every row in this matrix represents a polynomial which shares the roots of $\displaystyle f\bmod N$, then any integer linear combinations of them will once again yield a valid polynomial with the root $\displaystyle x_{0}$.

If there is such a polynomial $\displaystyle g( x)$ in this lattice satisfies $\displaystyle |g( x_{0})|< N$ then we have $\displaystyle g( x_{0}) =0$ since $\displaystyle |g( x_{0}) |$ is a multiple of $\displaystyle N$ it should be on the set $\displaystyle \lbrace...,-2N,-N,0,N,2N,...\rbrace$. We require $\displaystyle g$ to have small coefficients to satisfy this condition, specifically we require each coefficient $\displaystyle g_{i}$ of $\displaystyle g$ to satisfy

Since $\displaystyle B$ is triangular we have $\displaystyle \det(\mathcal{L}( B)) =\det( B) =B^{d( d+1) /2} N^{d}$. Now let $\displaystyle \mathbf{b}_{1}$ be the first vector in the $\displaystyle \delta$-LLL reduced basis where $\displaystyle \delta =3/4$ then we have

We interpret this vector as the coefficients of the polynomial $\displaystyle g( Bx)$ and by setting

we achieve the required bounds on the $\displaystyle g_{i}$ where $\displaystyle g_{i}$ is the $\displaystyle i$-th element of $\displaystyle \mathbf{b}_{1}$

Here is how we get the bound for $\displaystyle B$:

which give us the bound for $\displaystyle B$.

After LLL, we take the polynomial $\displaystyle g( Bx) =b_{0} +b_{1} x+b_{2} x^{2} +...+b_{d} x^{d}$, change it to $\displaystyle g( x) =b_{0} +\frac{b_{1}}{B} x+\frac{b_{2}}{B^{2}} x^{2} +...+\frac{b_{d}}{B^{d}} x^{d}$ and solve for its root, where $\displaystyle \mathbf{b}_{1}=(b_0,b_1,...,b_d)$

Example: Let $N=23 \times 29 = 667$ and $f(x)=x^2+6x+352 \in \mathbb{Z}[x]$ and has the small root $x_0 = 15\bmod N$.

from sage.all import *

def naive_small_roots(f,bound):
    # Modulus N
    N = f.parent().characteristic()
    f = f.change_ring(ZZ)
    P,(x,) = f.parent().objgens()
    if N == 0:
        raise ValueError
    d = f.degree()
    B = ZZ(bound)
    lc = f.leading_coefficient()
    if lc % N != 1:
        inv_lc = inverse_mod(lc,N)
        f = inv_lc * f

    # lift coefficient from Zmod(N) to ZZ 
    coeffs = []
    for i in range(d+1):
        a = ZZ(f[i]) % N
        if a > N//2:
            a -= N 
        coeffs.append(a) 
    M = Matrix(ZZ, d+1,d+1)
    roots = set()
    for i in range(d):
        M[i,i] = N * B**i
    for i in range(d+1): 
        M[d,i] = coeffs[i]*B**i 
    M = M.LLL()
    for row in M.rows():
        g = P(0)
        for i in range(d+1):
            g += (row[i] // B**i) * x**i 
        if g == 0:
            continue 
        for r in g.roots(multiplicities = False):
            if abs(ZZ(r)) <=B and ZZ(f(r)) % N == 0:
                roots.add(r) 
    return roots

P = PolynomialRing(Zmod(667), 'x')
x = P.gen()
f = x**2 + 6*x+352
r = naive_small_roots(f, 20)
print(r)
# {15}

Published 06 Jul 2026