How Prime Numbers Secure the Internet

When you open your banking app, send an iMessage, or enter a password on any site whose URL starts with https://, prime numbers are doing invisible work in the background. The reason your credit-card number doesn’t arrive at Amazon in plaintext is a piece of number theory from the 1970s called RSA — and the security of RSA rests on one fact: multiplying two big primes is easy, but factoring the product back into those primes is monstrously hard.

This article explains how that asymmetry becomes useful, what a “public key” actually is, and why a branch of pure mathematics with roots in ancient Greece turned out to be the foundation of digital privacy.

The one-way function at the heart of RSA

Most of classical cryptography is about shared secrets. Two parties agree on a key in advance, and use it to scramble and unscramble messages. That works fine between a spy and headquarters, but it’s hopeless for the internet — you can’t pre-share a secret with Amazon’s server before you’ve ever visited Amazon.

What you need is asymmetric cryptography: a scheme where anyone can lock a message, but only one specific recipient can unlock it. That sounds impossible at first. The breakthrough, in 1977, was realizing that certain mathematical operations are dramatically easier to perform in one direction than the other.

Multiplication vs. factoring is the archetype. Multiplying two 300-digit primes takes a laptop a fraction of a second. Factoring a 600-digit number back into its two primes, using the best classical algorithms known, would take billions of computers billions of years. That gap is the entire basis for RSA.

How RSA actually works

Here’s the recipe, stripped to essentials.

Key generation. A server picks two large primes $p$ and $q$ at random. It computes $N = p \cdot q$ and also $\phi(N) = (p-1)(q-1)$ — the number of integers less than $N$ that share no factor with it (Euler’s totient). It picks a public exponent $e$ (typically 65537, a common choice for efficiency) and computes a private exponent $d$ such that $e \cdot d \equiv 1 \pmod{\phi(N)}$.

The server publishes $(N, e)$ as its public key. It keeps $(p, q, d)$ secret.

Encryption. To send a message $m$ to the server, you compute

$c = m^e \bmod N$

and send the ciphertext $c$.

Decryption. The server recovers the message by computing

$m = c^d \bmod N$

The magic is that $m^{e \cdot d} \equiv m \pmod N$ — a consequence of Euler’s theorem, which says $m^{\phi(N)} \equiv 1 \pmod N$ for any $m$ coprime to $N$. Raising to the public exponent and then the private exponent cancels out, modulo $N$.

To break the system, an attacker needs $d$, which requires $\phi(N)$, which requires $p$ and $q$ — which requires factoring $N$. And that’s the hard part.

Why factoring is hard

If you’re asked to factor 15, you immediately see $3 \times 5$. Factor 91 and it takes a moment — $7 \times 13$. Factor a 10-digit number and most people need a calculator or paper. Factor a 60-digit number and the best trial-division approaches fail entirely; you need algorithms like Pollard’s rho or the quadratic sieve.

The best classical factoring algorithm, the general number field sieve, runs in roughly

$\exp\left((\log N)^{1/3} (\log \log N)^{2/3}\right)$

operations. That’s subexponential but still enormous for $N$ with hundreds of digits. RSA-2048 — the current recommended key size — has never been publicly factored, and isn’t expected to be with classical hardware this century.

Contrast that with the cost of multiplying two primes: quadratic in their length. A laptop multiplies 2048-bit numbers in microseconds.

This gap — polynomial in one direction, subexponential in the other — is what security experts call the “RSA assumption.” If someone found a polynomial-time factoring algorithm on a classical computer, RSA would collapse overnight. So far, nobody has.

Where the primes come from

A natural question: how does a server find two random 1024-bit primes? Trial division is hopeless. The trick is probabilistic.

Generate a random odd number of the right size. Test it with the Miller-Rabin primality test, which is fast and can declare non-primes with certainty while declaring likely primes with error below $2^{-100}$ if you repeat enough times. By the prime number theorem, roughly one in every $\ln(N) \approx 700$ odd numbers of that size is prime, so a few hundred random trials find one.

This is where the Riemann zeta function and the prime counting function $\pi(x)$ connect to practice. Cryptography cares about the density of primes — the guarantee that primes are common enough to find quickly, but thin enough to be hard to guess. Both facts flow from the analytic theory of primes. If the Riemann Hypothesis is ever disproved in a surprising way, the consequences for prime-finding algorithms could be significant.

What comes after RSA

RSA has been the internet’s workhorse for almost 50 years, but it’s gradually being replaced.

Elliptic curve cryptography (ECC) does the same job with much smaller keys by using the group law on elliptic curves instead of modular arithmetic. A 256-bit ECC key offers roughly the security of a 3072-bit RSA key. Modern TLS prefers ECC wherever possible.

Post-quantum cryptography looks ahead to the day when a large quantum computer can run Shor’s algorithm and break both RSA and ECC. NIST finalized its first post-quantum standards in 2024, based on problems in lattices and hash-based signatures — problems believed to remain hard even for quantum machines.

Both replacements still rely on the same strategic pattern: a mathematical operation that’s cheap in one direction and expensive in the other. That pattern, first exploited by RSA, is arguably the most important practical application of pure mathematics in the twentieth century.

What to take away

Prime numbers are not a dusty topic for competition-math nerds. They are the substrate of digital trust. Every secure connection you make today depends on someone, somewhere, having picked two big primes, multiplied them, and trusted that the result can’t be undone.

The beautiful, slightly vertiginous fact is that we don’t actually know factoring is hard. We believe it is because nobody has found a fast algorithm in 50 years of trying. If they did, most of the infrastructure of the internet would need to be rebuilt. Until then, ancient Greek number theory and modern commerce are stitched together by the same thread.

Frequently asked

Will quantum computers break RSA?

In principle, yes. Shor's algorithm can factor large numbers in polynomial time on a sufficiently large quantum computer. Current quantum hardware is nowhere near that scale, but the cryptography community is already migrating to post-quantum alternatives based on lattices and error-correcting codes.

How big do the primes have to be?

For RSA to be secure today, the modulus N = p·q should be at least 2048 bits long — that means each prime has around 300 decimal digits. 4096-bit keys are common for long-term security. Anything under 1024 bits is considered broken.

Continue reading

Formula

The Riemann Zeta Function

An infinite sum that hides the distribution of the primes. The object at the heart of the most important unsolved problem in mathematics.

Read →Person

Leonhard Euler

Swiss mathematician of extraordinary range and productivity. Formulated Euler's identity, founded graph theory, and produced more mathematical output than any mathematician before or since.

Read →Problem

Riemann Hypothesis

The most famous unsolved problem in mathematics. A proof would unlock dozens of other theorems in number theory.

Read →