Prime Factorisation
Easy to multiply together, astronomically hard to take apart
The Secret Behind Key Pairs
In our Asymmetric Encryption lesson, we saw that Bob uses a Public Key (a padlock everyone can close) and a Private Key (a key only Bob holds). But how does a computer actually create two keys where one key scrambles a message and only the other can unscramble it?
The secret foundation behind RSA and most public-key cryptography on the internet today is a simple mathematical property known as Prime Factorisation.
What is a Prime Number?
A prime number is an integer greater than 1 that has no positive divisors other than 1 and itself. In number theory, primes serve as the fundamental, indivisible building blocks of arithmetic: every composite number is uniquely formed by multiplying primes together:
2136,279,841 − 1 Discovered by researcher Luke Durant and GIMPS. If printed in a standard book, this single prime number would span more than 10,000 pages!
50+ Trillion Catalogued Over 2,300 years ago, Greek mathematician Euclid proved that primes never end. Humanity's supercomputers have catalogued over 50 trillion individual primes, with exact counts computed past 1028.
The One-Way Trapdoor: Multiplying vs. Factoring
Cryptography loves trapdoor functions: math operations that are effortless to perform in one direction, but practically impossible to reverse without a secret shortcut.
Secret Primes (p, q)
p = 61q = 53Kept secret by the key owner
Public Modulus (N)
N = 3,233 Published openly to the world
1. The Forward Direction: Trivial for Everyone
When your computer generates a key pair, it picks two secret
primes (p = 61 and q = 53) and
multiplies them: 61 × 53 = 3,233. Any smartphone,
laptop, or server computes this multiplication in a fraction of
a millisecond. The product N is distributed openly
as your padlock.
2. The Reverse Direction: The Attacker's Impossible Wall
An eavesdropper (like our spy koala) only sees the public
padlock N = 3,233. To forge your private key,
they must reverse the calculation by testing prime divisors one
by one. While 3,233 takes only a few dozen tries, a real
2048-bit key requires testing over 10⁶⁰ candidate primes, creating a 3.4-billion-year barrier!
Interactive Factoring Lab: Test Trial Division
Experience how classical computers attempt to factor public keys by testing prime divisors one by one. Select two secret primes (p and q) from the grid below, or pick a preset pair, then launch the eavesdropper attack!
Forge Your Key Pair: Select Secret Primes (p & q)
Click any two primes in the palette to pair them, or choose one of our quick presets:
⚡ Forward Direction: Computing p × q = N is instantaneous for any device (0.001 ms).
The Eavesdropper Attack: Cracking the Public Lock (N)
Watch the eavesdropper test candidate divisors against public
lock N.
🕵️ Eavesdropper Koala
"I intercepted public modulus N = 91! The
lock N is broadcast openly. But to forge Bob's signatures
and decrypt messages, I must crack it into secret primes p and q. Hit 'Crack with Trial Division' to
see how long it takes me!"
N into confidential primes p and q.
Click Crack with Trial Division to test candidate prime divisors against the public lock.
Why Classical Computers Can't Touch Real Keys
As you saw in the lab above, testing small numbers like 91 takes just a few attempts. Even numbers with a few thousand possibilities
take computers only a millisecond. So why is modern encryption considered
completely uncrackable?
N = 91
~4 Attempts
Factored in 0.0001 seconds on any phone or mental math.
N = 3,233
~25 Attempts
Factored in less than 1 millisecond by a computer.
N = 617 Digits
Over 10⁶⁰ Primes
3.4 Billion Years of uninterrupted classical supercomputing!
To factor a 2048-bit number by trial division, a classical computer would have to test more candidate numbers than there are atoms in the known galaxy! That is why RSA has been the rock-solid bedrock of global banking, passwords, and internet security for over 40 years.
