Skip to main content

dixon_factor

Function dixon_factor 

Source
pub fn dixon_factor(
    n: &BigInt,
    base: &[u64],
    tries: usize,
) -> Option<(BigInt, BigInt)>
Expand description

Dixon’s method: factor N via a congruence of squares found by a GF(2) dependency among smooth relations (see the module note above). Searches r = ⌈√N⌉, ⌈√N⌉+1, … for up to tries steps to gather relations whose r² mod N is smooth over base, then combines them. Returns (p, q) or None (not enough smooth relations found, or only trivial congruences). Reuses our GF(2) symmetry-breaking on RSA’s ring structure.