Module factor 

Structural factoring: the AIT thesis applied to public-key crypto.

The compressibility ladder crushes symmetric keystreams by finding their structure — a short feedback register, a correlation, a low-degree annihilator. RSA lives in a different universe: its security is integer factorization of N = p·q, not sequence structure. But the same thesis governs it. A weak RSA modulus is one with exploitable STRUCTURE, and every classical factoring attack is a structure-detector: a small factor, primes that sit too close, a smooth p−1, a shared prime across moduli, a small private exponent. Each such structure is a compression — a short description of the secret — and each attack returns a re-checkable WITNESS (the factors themselves, p·q = N).

The point of building the whole arsenal is the ceiling: run every structural attack against a soundly-generated modulus — two large, independent, well-separated strong primes — and it finds NOTHING within budget. RSA’s safety is precisely that its modulus is the number-theoretic incompressible residue: no structural shortcut exists, and only the general (sub-)exponential algorithms remain, which real key sizes push out of reach. Crush every structured form; the sound form stands. That standing IS the proof.

Structs

StructuralBudget

The effort budget for structural_factor: each structural attack runs to its own bound, then declines. A soundly-generated modulus exhausts every bound and yields no witness.

StructuralWitness

A certified structural weakness: the factors and the attack that found them.

Functions

batch_gcd

Batch GCD: catches a shared prime reused across moduli — the classic failure of low-entropy key generation. Any pair with gcd(Nᵢ, Nⱼ) > 1 hands over the common factor for free.

boneh_durfee

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.

common_modulus_attack

Common-modulus attack: recover m when the SAME message is sent to the same modulus N under two coprime public exponents e₁, e₂ (a key-reuse mistake). Bézout gives a·e₁ + b·e₂ = 1, so c₁ᵃ · c₂ᵇ = m^{a·e₁ + b·e₂} = m (mod N) — negative exponents handled by inverting the ciphertext.

coppersmith_factor_high_bits

Factor N from the high bits of one prime (Coppersmith’s method). We know p = p_high + x₀ with 0 ≤ x₀ < 2^unknown_bits; the monic linear polynomial f(x) = x + p_high has the small root x₀ modulo the unknown factor p. Coppersmith builds a lattice from the N-power and x-shift multiples of f (all vanishing modulo pᵐ at x₀), LLL-reduces it, and reads a short vector whose small root is an INTEGER root of a real polynomial — recovering x₀, hence p. This is the LATTICE lens: a factorization from PARTIAL knowledge that no factoring shortcut (Fermat, rho, p−1) can provide.

crt

Chinese Remainder Theorem: the unique x in [0, ∏mᵢ) with x ≡ residuesᵢ (mod moduliᵢ) for pairwise-coprime moduli, or None if a modular inverse fails (moduli not coprime).

dixon_factor

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.

factor_via_private_exponent

Factor N from the RSA private exponent d (Miller’s deterministic reduction). Since e·d − 1 is a multiple of λ(N), writing it as t·2ˢ and raising a base g to t·2ⁱ walks a chain that ends at 1; a step where the value squares to 1 while itself being ≠ ±1 is a NONTRIVIAL square root of unity, and gcd(x − 1, N) splits N. This is the converse of rsa_private_exponent: it proves that recovering the private key is computationally equivalent to factoring the modulus — the two are one problem, so RSA breaks exactly when N factors. Returns (p, q) or None (no base worked).

fermat

Fermat’s method: catches primes that sit too close — N = a² − b² with a just above √N, so a few steps expose (a−b, a+b). Structurally, close primes are a compressed key (one prime nearly fixes the other).

franklin_reiter_attack

Franklin–Reiter related-message attack: recover m from ciphertexts of two LINEARLY RELATED messages m and m + r (known r) under the same modulus N and a small public exponent e. Both g₁(x) = xᵉ − c₁ and g₂(x) = (x + r)ᵉ − c₂ have the root x = m mod N, so their GCD over (ℤ/N)[x] is the linear factor x − m, and m is read straight off it. The lens: two ciphertexts sharing a hidden root, extracted by polynomial GCD.

gcd

The greatest common divisor of |a| and |b| (Euclid).

hastad_broadcast_attack

Håstad’s broadcast attack: recover the plaintext m from k ≥ e ciphertexts cᵢ = mᵉ mod Nᵢ of the SAME message under a small public exponent e and distinct moduli (see the module note above). CRT reconstructs mᵉ exactly, and its integer e-th root is m. Returns the recovered message, or None if the CRT fails or the result is not a perfect e-th power (the precondition k ≥ e did not hold).

integer_nth_root

The integer n-th root ⌊x^{1/n}⌋ (Newton’s method, overestimate seed then monotone descent, exact final adjustment — the n-th-root analogue of isqrt).

is_probable_prime

Miller–Rabin primality over [MR_BASES].

isqrt

The integer square root ⌊√n⌋ (Newton’s method). The floating-point seed is only ~15 digits precise, so it is first forced to an OVERESTIMATE (x² ≥ n, a handful of doublings); from above, the Newton iteration x ← ⌊(x + ⌊n/x⌋)/2⌋ decreases monotonically and halts exactly at ⌊√n⌋.

low_exponent_message

Low-exponent / no-padding attack: if mᵉ < N (a small message under a small public exponent with no padding), then c = mᵉ over the integers, so the plaintext is just the integer e-th root of c.

mod_inverse

The modular inverse a⁻¹ mod m via the extended Euclidean algorithm, or None if gcd(a, m) ≠ 1.

modpow

Modular exponentiation base^exp mod m with a full BigInt exponent (square-and-multiply, the exponent’s bits read off by repeated halving).

next_prime

The smallest prime ≥ start.

pollard_p_minus_1

Pollard’s p − 1: catches a prime with a smooth p − 1. Raising a base to B! collapses to 1 modulo any prime whose p − 1 is B-smooth, and gcd(a − 1, N) exposes it — the smoothness is the structure.

pollard_rho

Pollard’s rho (f(x) = x² + 1, Floyd cycle detection): the general-purpose structural probe. Expected O(N^{1/4}), so it crushes moderate semiprimes but is bounded out on a large sound modulus.

quadratic_sieve

The quadratic sieve (see the module note above): factor N by log-sieving Q(x) = (⌈√N⌉+x)² − N over [0, m_interval) against the factor base of primes ≤ b for which N is a quadratic residue, then combining smooth relations through a GF(2) dependency. Returns (p, q) or None.

rsa_private_exponent

Derive the RSA private exponent d = e⁻¹ mod φ(N) from the public exponent and the two primes (φ = (p−1)(q−1)), or None if e is not coprime to φ. The “if you can factor, you can break RSA” direction: the factorization hands over the private key.

structural_factor

Run the whole structural arsenal against n within budget, returning the first certified factorization found, or None — the number-theoretic incompressible residue (a sound modulus has no structural shortcut, so only the general sub-exponential algorithms, out of scope here, remain).

trial_division

Trial division up to limit: catches a small factor — a modulus that leaked a tiny prime.

verify_factorization

A nontrivial factorization p·q = n (1 < p, q < n) — the re-checkable witness every attack returns.

wiener

Wiener’s attack: catches a small private exponent d (d < ⅓ N^{1/4}). The convergents of the continued fraction of e/N include k/d; from d we recover φ(N), then p, q as roots of x² − (N − φ + 1)x + N. A small d is a compressed private key — and this reuses the very continued-fraction / rational-reconstruction machinery the 2-adic FCSR rung was built on.