Skip to main content

boneh_durfee

Function boneh_durfee 

Source
pub fn boneh_durfee(
    n: &BigInt,
    e: &BigInt,
    m: usize,
    t: usize,
    x_bound: &BigInt,
) -> Option<(BigInt, BigInt)>
Expand description

Boneh–Durfee: recover the factorization from a small private exponent d < N^{0.284} — beyond Wiener’s N^{0.25} — by bivariate Coppersmith. Since e·d − 1 = k·φ(N) and φ(N) = N + 1 − (p+q), the polynomial f(x, y) = x·y + (N+1)·x + 1 has the small root (x₀, y₀) = (k, −(p+q)) modulo e. The lattice of x- and y-shifts of f, LLL-reduced (fast float-Gram-Schmidt), yields short bivariate polynomials sharing that root; a resultant eliminates x, its root gives s = p+q, and z² − s·z + N splits N. m, t size the lattice; x_bound = N^δ bounds k. Returns (p, q) or None.