The Ancient Numbers That Secure the Internet

Right now, as you read this, a number with 617 digits is protecting your banking session. It is the product of two prime numbers, each roughly 300 digits long, chosen at random from among the primes that exist near those scales.

The person who wants to read your traffic without authorization must factor that 617-digit number, finding the two primes that were multiplied together to produce it. With the best classical computers and algorithms known, that would take longer than the current age of the universe. Not because the problem is theoretically impossible. Not because the mathematics is impenetrable. The gap between multiplying two numbers and factoring their product is trivial for small numbers and astronomically wide for large ones.

This asymmetry is the entire foundation of public-key cryptography. It is a property of prime numbers that was noticed by mathematicians who had no engineering application in mind, in a tradition of inquiry that stretches from ancient Athens to twentieth-century universities, until one day in 1977 three MIT researchers sat down and turned it into a lock that the whole world could use.

What Makes a Number Prime: Why They Never Run Out

A prime number is a positive integer greater than 1 that has no divisors other than 1 and itself. The first few: 2, 3, 5, 7, 11, 13, 17, 19, 23. The number 2 is the only even prime. Every other prime is odd. They appear to thin out as numbers grow larger, but they never stop.

Euclid's proof of the infinitude of primes, appearing in Book IX of the Elements around 300 BC, is one of the most elegant arguments in all of mathematics. Suppose, he said, that there are only finitely many primes: $p_1, p_2, \ldots, p_n$. Multiply them all together and add 1. Call this number $N = (p_1 \times p_2 \times \cdots \times p_n) + 1$. $N$ is either itself prime (a new prime not on the list) or divisible by some prime. But it cannot be divisible by any prime on the list. Dividing $N$ by any $p_i$ leaves a remainder of 1. Therefore there must be a prime not on the list. Either way, the list was incomplete. Contradiction. No finite list can contain all primes.

The proof stands today exactly as Euclid wrote it. No refinements needed in 2,300 years.

Eratosthenes followed about 60 years later with the practical companion to Euclid's proof: a method for finding the primes themselves. Start from 2, cross out all its multiples, advance to the next uncrossed number, repeat. Every uncrossed number is prime. The primes thin out but never disappear. The Prime Number Theorem tells us that near a large number $n$, primes are spaced approximately $\ln(n)$ apart. Near $2^{2048}$, that spacing is about 1,419. Roughly 1 in every 1,419 numbers at that scale is prime. Rare, but still abundant enough to find easily by random search.

The Asymmetry That Protects Everything

The Fundamental Theorem of Arithmetic says something simple and remarkable: every integer greater than 1 can be broken down into prime numbers, and there is only one way to do it. The number 12 breaks down as $2 \times 2 \times 3$ (or, written compactly, $2^2 \times 3$). No other combination of primes multiplies to 12. Not $4 \times 3$, because 4 is not prime. Not $6 \times 2$, because 6 is not prime. The prime factors of an integer are unique to that integer, like a mathematical fingerprint.

The number 360 breaks down as $2^3 \times 3^2 \times 5$, which is $2 \times 2 \times 2 \times 3 \times 3 \times 5$. Again, no other combination of primes produces 360. Every integer has its own prime fingerprint, and no two integers share the same one.

This uniqueness is what makes prime factorization the only path to certain facts about a number. If someone hands you 3,233, you cannot know its prime factors without doing the factoring work. There is no shortcut, no clever pattern, no algebraic manipulation that reveals "3,233 = 53 × 61" faster than actually trying to factor it. The information is locked inside the number, and the only key is to factor.

Now for the asymmetry that makes cryptography possible. Choose two large prime numbers, say each 1,024 bits long (roughly 308 decimal digits). Multiply them together. The multiplication takes a fraction of a millisecond on any modern computer. The resulting 2,048-bit number can be handed to anyone in the world. Now ask them to reverse the process: given only the product, find the two original primes.

For small numbers like 3,233, factoring is trivial. Trial division finds $53 \times 61$ in milliseconds. For a 617-digit number, trial division would take longer than the heat death of the universe. This gap, negligible for small inputs and astronomical for large ones, is the engineering foundation of RSA.

Six Steps From Two Primes to a Working Lock

In 1977, Ron Rivest, Adi Shamir, and Leonard Adleman at MIT formalized the first practical public-key cryptosystem based on prime factoring difficulty. Here is exactly how RSA works. No hand-waving, no analogy-only explanation. The numbers below are deliberately small for clarity; production RSA uses primes ~1,024 bits long.

Before the steps, one concept to keep in mind. RSA lives entirely in modular arithmetic: clock arithmetic. When we write $17 \bmod 5 = 2$, we mean "divide 17 by 5, take the remainder." Mod wraps the number line into a loop. On a 12-hour clock, 14:00 mod 12 is 2:00. Every operation that follows happens on a number line that wraps around at $n$.

Step 1. Choose two large prime numbers $p$ and $q$.

$$p = 61, \quad q = 53 \quad \text{(in practice: }{\sim}1024\text{ bits each)}$$

Chosen randomly. The security of RSA depends entirely on these remaining secret. They are chosen from among primes of the required size using a randomized primality test (Miller-Rabin). Finding large primes is fast; factoring large composites is hard.

Step 2. Compute the modulus $n$ and Euler's totient $\varphi(n)$.

$$n = p \times q = 61 \times 53 = 3{,}233$$

$$\varphi(n) = (p - 1)(q - 1) = 60 \times 52 = 3{,}120$$

$n$ is the public modulus, the number everyone sees. $\varphi(n)$ is Euler's totient: it counts how many integers from 1 to $n$ share no common factor with $n$ other than 1. For a quick sanity check, $\varphi(10) = 4$, because in the range 1 to 10, exactly four numbers share no common factor with 10: namely 1, 3, 7, and 9. This is the mathematical trapdoor: $\varphi(n)$ is trivial to compute if you know $p$ and $q$, impossible to compute efficiently from $n$ alone.

Step 3. Choose a public exponent $e$.

$$e = 17 \quad \text{such that } 1 < e < \varphi(n) ;\text{and}; \gcd(e, \varphi(n)) = 1$$

In practice, $e = 65{,}537$: a prime that makes encryption fast. (gcd is the greatest common divisor, the largest integer that divides both numbers. $\gcd(12, 18) = 6$. $\gcd(7, 11) = 1$, the case we want here, called "coprime".)

$65{,}537 = 2^{16} + 1$ has only two 1-bits in binary, making modular exponentiation efficient. It is by far the most common public exponent in deployed RSA systems worldwide. Public key $= (n, e)$. This pair is shared freely.

Step 4. Find the private exponent $d$, the mathematical inverse of $e$.

$$d \times e \equiv 1 \pmod{\varphi(n)}$$

$$d \times 17 \equiv 1 \pmod{3{,}120} \quad\Longrightarrow\quad d = 2{,}753$$

The notation $a \equiv b \pmod{m}$ means $a$ and $b$ leave the same remainder when divided by $m$. So we want a $d$ such that $d \times 17$ wraps around the 3,120-clock and lands exactly on 1. That $d$ is called the modular inverse of $e$, and it is found via the Extended Euclidean Algorithm in microseconds.

$d$ is the private key, known only to the key owner. Finding $d$ requires knowing $\varphi(n)$, which requires knowing $p$ and $q$. An attacker who only knows $n$ and $e$ cannot compute $d$ without first factoring $n$. Private key $= (n, d)$. Kept absolutely secret.

Step 5. Encryption uses the public key.

$$C = M^e \bmod n$$

$$M = 65 \quad\Longrightarrow\quad C = 65^{17} \bmod 3{,}233 = 2{,}790$$

Anyone with your public key $(n, e)$ can encrypt a message $M$. The ciphertext $C$ is computed by fast modular exponentiation, efficient even for 2048-bit numbers via the "square and multiply" algorithm (which computes $M^e$ in roughly $\log_2 e$ multiplications instead of $e$). $C$ reveals nothing about $M$ to anyone who does not know $d$.

Step 6. Decryption uses the private key.

$$M = C^d \bmod n$$

$$2{,}790^{2753} \bmod 3{,}233 = 65 ; \ \checkmark$$

Raising the ciphertext to the power $d$ and reducing mod $n$ recovers the original message exactly. Why does this work? Euler's theorem (a generalization of Fermat's little theorem to non-prime moduli) tells us that for any $M$ with $\gcd(M, n) = 1$:

$$M^{\varphi(n)} \equiv 1 \pmod{n}$$

Since $e \cdot d \equiv 1 \pmod{\varphi(n)}$, we can write $e \cdot d = k\varphi(n) + 1$ for some integer $k$. Then:

$$C^d = M^{e \cdot d} = M^{k\varphi(n)+1} = M \cdot \bigl(M^{\varphi(n)}\bigr)^k \equiv M \cdot 1^k \equiv M \pmod{n}$$

The mathematics closes perfectly.

What is remarkable about this construction is that the public key $(n, e)$ and the private key $(n, d)$ are mathematically related. $d$ is the modular inverse of $e$ with respect to $\varphi(n)$. But the relationship can only be computed if you know $\varphi(n)$, and $\varphi(n)$ can only be computed if you know $p$ and $q$, and $p$ and $q$ can only be found by factoring $n$. The whole tower of security rests on that single computational difficulty at the base.

RSA does not hide the lock. It puts the lock in plain sight and dares anyone to open it. The genius is that the lock is made of mathematics so hard that "plain sight" confers no advantage whatsoever.

— Paraphrase of Rivest, Shamir, Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" (1978)

How Hard Is Hard, Exactly?

"Computationally difficult" is not a vague claim. The difficulty of integer factoring is measured precisely, and the numbers are genuinely humbling. The first public factoring challenge was set in 1977 by Martin Gardner's Scientific American column (the famous RSA-129); RSA Laboratories launched the formal RSA Factoring Challenge in 1991 with prizes for factoring increasingly large semiprimes from RSA-100 upward. The results map the moving frontier of what is actually possible.

The frontier moves slowly and predictably. Every doubling of key length pushes the classical attack horizon out by orders of magnitude. The reason 2,048 bits has held since the 1990s is not that nobody has tried. It is that nobody has tried enough, by a factor of about a trillion.

Diffie-Hellman, Discrete Logarithms, and Elliptic Curves

RSA is not the only cryptographic system built on number-theoretic hardness. Two other problems from number theory, the discrete logarithm problem and the elliptic curve discrete logarithm problem, underpin the other major systems in use today.

Diffie-Hellman key exchange

Whitfield Diffie and Martin Hellman's 1976 paper introduced the concept of public-key cryptography before RSA existed. Their key exchange protocol relies on the discrete logarithm problem: given a prime $p$, a generator $g$, and the result $g^x \bmod p$, find $x$. Computing $g^x \bmod p$ (modular exponentiation) is fast. Finding $x$ given the result is computationally hard. No polynomial-time classical algorithm is known for the general case.

(A generator $g$ for a prime $p$ is a number whose powers cycle through every nonzero value mod $p$: the sequence $g^1, g^2, g^3, \ldots, g^{p-1} \bmod p$ visits every integer from 1 to $p-1$ exactly once. The discrete logarithm is the modular-arithmetic cousin of an ordinary logarithm: if $g^x = y$ over real numbers, the log gives you $x$ directly. In modular arithmetic, the same problem becomes enormously harder.)

$$A = g^a \bmod p \qquad B = g^b \bmod p$$

$$K = A^b \bmod p = B^a \bmod p = g^{ab} \bmod p$$

The mechanics:

• $g, p$ — public parameters. A prime $p$ and a generator $g$ are shared openly. Everyone knows them. Security does not depend on their secrecy.
• $a, b$ — private exponents. Alice and Bob each choose these secretly and never transmit them. The eavesdropper sees only $g^a \bmod p$ and $g^b \bmod p$, and cannot compute $g^{ab} \bmod p$ without solving the discrete log problem.
• Security. Finding $a$ from $g^a \bmod p$ is the discrete logarithm problem. No efficient classical algorithm is known. The best attacks are sub-exponential, similar in character to factoring and similarly secure at appropriate key sizes.
• TLS 1.3. Every HTTPS connection your browser makes negotiates a session key using a variant of this exchange (ECDHE, elliptic curve Diffie-Hellman ephemeral). The padlock in your browser represents this happening.

Elliptic Curve Cryptography

Elliptic curves are not ellipses. They are curves of the form $y^2 = x^3 + ax + b$ defined over a finite field: a set of numbers where arithmetic wraps around at some prime $p$. The integers mod $p$ are the simplest finite field; the only values that exist are 0 to $p-1$, and addition and multiplication wrap around at $p$. Elliptic curves over a finite field have integer coordinates only, so the smooth curve from high-school algebra becomes a scattered cloud of discrete points.

These curves have a geometric operation called point addition that, when applied repeatedly, creates a discrete logarithm problem of its own. Given a starting point $G$ on the curve and a result $Q = kG$ (applying the addition $k$ times), finding $k$ is computationally hard.

The security of ECC does not rest on prime factoring difficulty. It rests on the elliptic curve discrete logarithm problem, a different hard problem with no known sub-exponential attack. This is why ECC keys are much shorter than RSA keys for equivalent security, and why ECC has become the default for most new cryptographic deployments.

What Happens When Shor's Algorithm Runs on Real Hardware

Peter Shor's 1994 quantum algorithm factors integers in polynomial time: $O((\log n)^3)$ operations on a quantum computer. It also solves the discrete logarithm problem in polynomial time. Both RSA and Diffie-Hellman are completely broken by a sufficiently powerful quantum computer. A quantum computer capable of running Shor's algorithm on 2048-bit RSA keys would require on the order of 4,000 to 6,000 fault-tolerant logical qubits, which Gidney and Ekerå's 2021 analysis estimated translates to approximately 20 million physical qubits running for about 8 hours. Recent 2025 work has suggested this could fall below 1 million physical qubits with improved error-correction schemes, but no machine in either range exists today. The largest gate-based quantum computers in 2026 sit in the hundreds to just over one thousand physical qubits, and the error rates are nowhere near low enough.

The threat is real but the timeline is measured in decades, not years. The engineering response, post-quantum cryptography, is already underway. In August 2024, NIST finalized three post-quantum standards: CRYSTALS-Kyber (FIPS 203, renamed ML-KEM — key encapsulation, based on learning-with-errors, a lattice problem), CRYSTALS-Dilithium (FIPS 204, renamed ML-DSA — digital signatures), and SPHINCS+ (FIPS 205, renamed SLH-DSA — hash-based digital signatures). A fourth algorithm, FALCON (slated as FIPS 206 / FN-DSA), is still being standardized. These are based on mathematical problems that Shor's algorithm does not solve. Problems from lattice theory and hash functions rather than number theory. The global migration to post-quantum cryptography is the most important cryptographic engineering project of the decade.

The broader implication: prime-based cryptography is not being broken by better mathematics. It is being threatened by a completely different computational model that happens to solve a specific number-theoretic problem efficiently. The mathematics of prime numbers remains as hard as it ever was for classical computers. The quantum computer sidesteps the hardness rather than cracking it.

What 2,300 Years of "Useless" Mathematics Actually Built

The story of prime numbers and cryptography is one of the clearest examples in history of a principle that engineers should internalize: no area of mathematics is permanently without application. Euclid studied prime numbers because they are the atoms of arithmetic, fundamental objects of genuine mathematical interest. Fermat and Euler developed modular arithmetic in the seventeenth and eighteenth centuries to understand the structure of numbers, not to encrypt communications. Gauss worked on prime distribution in the nineteenth century as a pure mathematical question. None of them had any conceivable engineering application in mind.

Then, in 1977, Rivest, Shamir, and Adleman discovered that the specific difficulty of a specific mathematical problem (factoring the product of two large primes) could be made into a lock. The tools had been sitting in the mathematical literature for centuries, waiting for someone to recognize what they were actually good for. The lock they built now secures trillions of dollars of daily commerce, protects communications for billions of people, and authenticates every software update running on every internet-connected device in the world.

Euclid's proof of the infinitude of primes is, in a very direct sense, the mathematical theorem on which the security of the internet rests. Not because anyone planned it that way. Because mathematics has a tendency to turn out useful in ways that nobody anticipated, and the people who study it for its own sake are, inadvertently and generously, doing engineering for a future they cannot see.

The number 65,537 is the most important constant in everyday cryptography. The public exponent in RSA is almost always $65{,}537$, written as 0x10001 in hexadecimal, equal to $2^{16} + 1$. It was chosen because it is prime (so $\gcd(65537, \varphi(n)) = 1$ is easily satisfied), large enough to avoid certain small-exponent attacks, and crucially has exactly two 1-bits in binary ($10000000000000001_2$). The "square and multiply" algorithm for modular exponentiation needs only 16 squarings and 1 multiplication to compute $M^e \bmod n$. Any other prime would require more.

The choice of $e = 65{,}537$ is not arbitrary engineering convenience. It is the product of careful analysis of mathematical structure, attack surface, and computational efficiency. The same kind of reasoning that runs through all of cryptography. The number sitting in the public key of every RSA certificate on the internet was put there for reasons that require number theory to understand fully.