The RSA Factoring Sandwich

Charles Dana (Tulane University, Monce SAS) & Claude (Anthropic)
April 2026 | Living document | v1.0.0

1. Introduction

Integer factorization is believed to lie in the grey zone between P and NP-complete. It sits in NP ∩ coNP — verifiable in both directions — yet no polynomial algorithm is known, and no NP-hardness reduction exists. RSA's security rests on this ambiguity.

Rather than asking "is factoring hard?", we ask: how much of the factoring landscape is actually hard? Following the P/NP/P sandwich framework from polynomial Sudoku solving and PolySAT, we decompose the space of n-bit semiprimes into polynomial zones flanking an NP strip, parameterized by a budget exponent a.

2. The Sandwich Structure

For an n-bit semiprime N = p × q:

2.1 Budget Model

Following cdcl(a) from the Sudoku paper, we parameterize the total number of arithmetic operations as:

For fixed a, this is polynomial in n. Each technique receives a fraction of the budget. The wall — the bit size where the technique ladder fails — moves rightward as a increases.

2.2 Technique Ladder

3. Pollard's Rho and the Exponential Wall

Pollard's rho is the workhorse. Its expected complexity is O(N^1/4) = O(2^n/4) GCD operations. Within a polynomial budget n^a:

For n = 50: a ≥ 50 / (4 × 5.64) ≈ 2.2 — rho fits comfortably in n^2.5.
For n = 100: a ≥ 100 / (4 × 6.64) ≈ 3.8 — needs n⁴.
For n = 200: a ≥ 200 / (4 × 7.64) ≈ 6.5 — "polynomial" budget is n^6.5.
For n = 2048 (RSA-2048): a ≥ 2048 / (4 × 11) ≈ 46.5 — n⁴⁷ operations.

The required exponent grows linearly with n. This is the same phenomenon as Sudoku's n=5 mid-strip: the "polynomial" budget must grow so fast with problem size that it becomes effectively exponential. The polynomial framing doesn't break — for any fixed a, the budget is polynomial — but the a needed to solve grows with n, destroying the polynomial guarantee.

4. Fourier Probing on Multiplication

AUMA's Fourier probe (order-1 Walsh-Hadamard coefficients) scores each bit position of a candidate factor by evaluating N mod x with targeted bit flips. The hope: some bits of p have stronger "signal" than others.

Result: low-order bits show detectable bias (the LSB is always 1 for odd primes; bit 1 has mild correlation with N mod 4). High-order bits show no signal — the carry chain from multiplication acts as a diffusion mechanism, exactly like SHA-256's message schedule in the PolySAT experiments.

This mirrors the PolySAT finding: moulinette achieves 93.5% structural novelty on SHA-256 CNF but zero hardness reduction. Cryptographic diffusion — whether from hash functions or multiplication carries — defeats syntactic/Fourier analysis.

5. Comparison with Sudoku and SAT

The key difference: factoring has algebraic structure that Sudoku and SAT lack. The number field sieve exploits smoothness in algebraic number fields — something invisible to any Boolean/SAT encoding. Our sandwich captures the combinatorial hardness but cannot account for algebraic shortcuts.

6. Empirical Results — Potato Benchmark

All benchmarks run on a single t3.micro (2 vCPU, 1GB RAM, ~$7.50/month) — the cheapest general-purpose EC2 instance. Pure Python, zero dependencies, no C extensions. The sandwich eats composites of any shape: semiprimes, highly composite numbers, prime powers. Recursive factorization splits until all factors are confirmed prime via Miller-Rabin.

6.1 Semiprime Climb (a = 4.0, 3 samples per level)

The 100-bit semiprime 999924788784990627355480102499 = 951533318763589 × 1050856306413191 was factored in 24 seconds on the potato at a=4.5. Brute-force trial division to √N would require ~2²⁵ ≈ 33M divisions; Pollard's rho with 3 restarts (different random walks, same total budget) finds the birthday collision in ~65M iterations.

6.2 Wall Movement with Exponent

Two views of the same data: the budget wall (unlimited time, does the budget suffice?) and the time wall (1-second timeout, can the potato finish?).

Budget wall (no time limit)

Budget wall retreats monotonically: more budget = more bits cracked.

Time wall (1s timeout per factorization)

The time-optimal exponent is a=4.0, not higher. Past a=4.0, the budget grows faster than the potato can execute — rho has enough evaluations to find the factor but can't finish them in 1 second. The wall retreats from 86b back to 62b at a=5.0. This is a new dimension the Sudoku paper doesn't explore: when wall-clock time constrains, there's a Goldilocks exponent where budget is large enough to solve but small enough to complete.

For the potato (~50M rho-ops/sec) with T=1s: a* ≈ 4.0. On faster hardware, a* shifts rightward. The Goldilocks exponent is a property of the machine-algorithm pair, not the problem alone.

6.3 Technique Attribution — Rho Is Everything

At a=3.0, 10 balanced semiprimes per bit size (1s timeout):

Trial division dominates to ~20 bits, then rho takes 100% of wins from 25-50 bits. At the boundary (55-60b), pm1 starts sneaking in — when rho's budget runs out, pm1 occasionally catches a factor with smooth p-1. By 60 bits, 4/10 instances fail entirely.

Fermat never fires on balanced semiprimes — rho runs before it. On close-factor pairs (|p-q| < 200), Fermat solves in 1 eval, but rho steals the kill. The technique order matters: rho's 40% budget slice runs second, Fermat's 10% runs fifth.

The honest summary: past trial division, the "sandwich" on balanced semiprimes is really a rho dial. The other techniques matter for structured composites (pm1 for smooth factors, Fermat for close factors, trial for highly composite numbers), but RSA-hard instances live where only rho reaches.

6.4 Fourier Probe — Negative Result

AUMA-inspired Fourier probing (order-1 bit scoring via N mod x with targeted flips) was tested head-to-head against rho on 50 samples per bit size, tight budget n²:

Fourier probe wins exactly 0 out of 350 trials. Not once. The carry chain in integer multiplication diffuses bit-level structure identically to SHA-256's message schedule in the PolySAT experiments. Low-order bits show mild bias (LSB is always 1 for odd primes), but high-order bits are indistinguishable from random. This is the same wall as moulinette's 93.5% structural novelty / 0% hardness reduction on SHA-256 CNF — cryptographic diffusion defeats Fourier analysis, whether the diffusion comes from hash rounds or multiplication carries.

6.5 Restarts — The 10x Method on Rho

Pollard's rho is probabilistic: a single random walk may cycle without finding a factor. The 10x method from Sudoku applies: split the budget into 3 attempts with different c values.

30-sample comparison per bit size (a=3.0 budget, 1s timeout):

At the boundary (60b), restarts provide a marginal +1 net advantage. But at 70 bits, restarts hurt: net -3. Splitting the budget into shorter walks means each attempt is too brief for rho to build enough GCD state. Single-shot with the full budget works better when the walk needs to be long.

This is the opposite of Sudoku's 10x result. Sudoku walks are binary — they solve in the first 10% of budget or never. Rho's success curve is gradual: the probability of finding a collision grows with walk length. Cutting walks short doesn't just waste a failed attempt — it prevents successful walks from reaching their collision. The 10x method transfers to methods with early-knowledge success profiles, not to methods with cumulative-state profiles like rho.

6.6 Any Composite — Recursive Factorization

The /factor endpoint accepts any integer and recursively splits until all factors are confirmed prime via Miller-Rabin.

Unbalanced semiprimes are trivial — trial division finds the small factor in ~300 evals regardless of how large the cofactor is. Prime powers are instant — perfect-power detection in the trivial checks catches them. Smooth numbers are sub-millisecond — P-Right peels factors of 2 and 3, trial division catches the rest. The only hard shape is balanced semiprimes, where both factors are large and structureless.

7. The Sandwich on RSA Key Sizes

The potato cracks everything up to 100 bits. The real contribution is the continuous complexity dial: by measuring where the wall hits as a function of a, we map the exact boundary between "polynomial enough" and "effectively exponential." Try it yourself: /factor any integer, /climb to find the wall.

8. Conclusion

The sandwich framework applies cleanly to integer factorization. A t3.micro potato cracks 100-bit semiprimes in 24 seconds with polynomial budget n^4.5. The budget wall tracks rho's birthday bound at a ≥ n/(4 log n) within ~10%. This is the same mechanism as Sudoku's n=5 mid-strip and PolySAT's SHA-256 core: "polynomial with growing exponent" is how combinatorial hardness manifests across all three domains.

Three findings that surprised us:

1. Rho is everything. Past 25 bits, Pollard's rho accounts for 100% of balanced-semiprime factorizations. Fourier probing: 0/350. Fermat and pm1 never fire on RSA-shaped inputs. The technique ladder matters for structured composites (unbalanced, smooth, close-factor), but the NP strip — where RSA keys live — belongs entirely to rho.

2. The Goldilocks exponent. Under wall-clock constraints, there exists a time-optimal exponent a* where the wall is deepest. On the potato with 1s timeout: a*=4.0 (wall at 86b). Higher exponents have enough budget but can't finish — the wall retreats from 86b at a=4.0 to 62b at a=5.0. This is a machine-algorithm property, not a problem property. The Sudoku paper treats budget as the only dimension; real systems have a second axis (time) that creates a non-monotonic optimum.

3. Restarts hurt rho. The 10x method — cheap fast failures + more attempts — works beautifully on Sudoku walks (binary success profile). On rho, it backfires at 70 bits: net -3 vs single-shot. Rho has a cumulative-state success profile — collision probability grows with walk length. Cutting walks short prevents successful walks from reaching their collision. The 10x method transfers to early-knowledge methods, not cumulative-state methods.

Factoring's escape hatch — algebraic structure in NP ∩ coNP — means the combinatorial wall is not the whole story. The number field sieve operates in sub-exponential time L_n[1/3, c], suggesting the NP strip may be thinner than for NP-complete problems. The sandwich captures the combinatorial hardness faithfully; whether algebraic tunnels can bypass it remains the central open question.

References:
[1] Dana, C. "A O(2^n/2) Universal Maximization Algorithm." Ecole Polytechnique, 2023.
[2] Dana, C. & Claude. "Polynomial Sudoku Solving and the P/NP Sandwich." March 2026.
[3] Dana, C. & Claude. "PolySAT: 12 Polynomial Techniques on SAT." March 2026.
[4] Dana, C. & Claude. "polyauma: Universal Maximization in Polynomial Budget." March 2026.
[5] Pollard, J. M. "A Monte Carlo method for factorization." BIT, 1975.
[6] Lenstra, H. W. "Factoring integers with elliptic curves." Annals of Mathematics, 1987.
[7] Lenstra, A. K. et al. "The number field sieve." STOC, 1990.