! Educational demonstration only. Keys, moduli, and RSA sizes here are intentionally tiny so classical/quantum attacks finish in seconds — today's classical hardware cannot run Shor's algorithm against real production RSA keys. See Security & Limitations.
Shor's Lab

Run this project's four from-scratch classical factoring attacks (attacker/classical.py) against a composite number, side by side.

0. How each attack actually works, step by step

try your own composite — every stage below recomputes for real, and the tool below stays in sync

Step 1 of 4: Trial division. Check every possible divisor up to √n. Always correct eventually — but painfully slow for large n.

trying every candidate divisor of 8051, one at a time

8051 ÷ 6…
d=2√n = 89

O(√n) — has to reach 83 before it finds anything

n mod d=0,d=2,3,…,⌊8051⌋=89n \bmod d = 0, \quad d = 2, 3, \dots, \lfloor\sqrt{8051}\rfloor = 89

01Check every possible divisor up to √n. Always correct eventually — but painfully slow for large n.

The actual code behind this step

attacker/classical.py:88-97
    limit = math.isqrt(n)
    d = 3
    while d <= limit:
        operations += 1
        remainder = n % d
        if trace is not None:
            trace.append(TrialDivisionStep(d, remainder, remainder == 0))
        if remainder == 0:
            elapsed = time.perf_counter() - start
            return FactorAttemptResult(n, "trial_division", d, n // d, operations, elapsed, True, trace=trace)

1. Run all four attacks live

Using n = 8051 — change above.

Replay: trial division, one divisor at a time

The real attempt log for n = 8051 -- every odd divisor trial division actually tried, in order, not just the final operations count.

Trial division

Tries every divisor up to √n. Fast only when n has a small factor -- O(√n) in general.

Fermat's method

Expresses n = a² − b². Extremely fast when the two prime factors are close together -- a real historical implementation bug class.

Pollard's rho

General-purpose cycle-detection method, expected ~O(n^(1/4)) -- better than trial division for generic composites.

Pollard's p-1

Succeeds fast only when p−1 (or q−1) is "smooth" (all small prime factors) -- defended against by choosing safe primes.

None of these demonstrations scale to real RSA key sizes (2048+ bits) -- see the Classical Benchmark page for measured evidence of the exponential growth.