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.