python-pollard-rho-brent-ecm-factorization

Answer

Delivered a verified solution. Files:

• ~/factor.py — the complete pipeline (stdlib only)
• ~/SOLUTION.md — self-contained write-up with the full embedded code, analysis, and verification

Summary

Root causes of failure in a naive pipeline 1. Pollard rho is asymptotically too slow for balanced 120-bit semiprimes (~2^30 ops) — ECM must carry the load. 2. Prime/perfect powers (p^k) must be detected up front via exact integer k-th roots over prime exponents only. 3. The critical BSGS bug: in stage 2 the pair (m=1, j=D) represents the value 0 with G_1 = D·Q = baby[D], so its cross product is identically 0, poisoning the running product mod all of n and making every gcd return n. 4. x-only Montgomery arithmetic can't distinguish P from −P; BSGS must cover both mD+j and mD−j. 5. gcd must be batched, not called per point.

The exact fix (in _ecm_curve stage 2):

for j in range(1, D + 1):
    if m * D == j:        # m*D - j == 0 -> point at infinity
        continue
    ...
    cross = (gx * bzj - bxj * gz) % n
    acc = acc * cross % n

The implementation also includes: Miller-Rabin, exact perfect-power detection, Brent rho, Pollard p-1, Suyama-parametrized ECM with x-only Montgomery ladder, stage-1 batched gcd, and the BSGS stage 2 with cross-curve batch gcd.

Verification - Built-in selftest passes (python3 factor.py). - 400 random mixed-size cases (20–120 bits): all products correct, all factors prime. - 50 balanced 120-bit semiprimes (two fresh 60-bit primes): max 23.67 s, median 3.59 s, mean 5.53 s, all correct. - Stage-2-only success after the fix: 2/20 → 20/20. - Baby/giant chains validated against the Montgomery ladder by projective-coordinate equality.

Scope note: the final tier (B1=250000, 400 curves) is the catch-all; I measured no case that exhausted all four tiers, so the _split fallback is unreachable in practice for ≤120-bit semiprimes.