How Prime Numbers Underpin Modern Cryptography and Secure the Internet

The Lock on Every Online Transaction

When you enter a credit card number on a website, the data is encrypted using a system that depends on a mathematical fact: multiplying two large prime numbers together is easy, but reversing the process—finding those two primes from their product—is extraordinarily hard. A modern computer can multiply two 300-digit primes in milliseconds. Factoring their 600-digit product back into those primes would take longer than the age of the universe using the best known classical algorithms.

This asymmetry between multiplication and factoring is the foundation of RSA encryption, the most widely deployed public-key cryptosystem in history. Invented in 1977, RSA secures banking, email, government communications, and virtually every HTTPS connection on the internet.

Primes: The Atoms of Number Theory

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The sequence begins 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... Euclid proved around 300 BCE that there are infinitely many primes. The proof is elegant: assume a finite list of all primes, multiply them together, add 1, and the result is not divisible by any prime on the list—contradicting the assumption.

The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be expressed as a unique product of prime factors. This uniqueness is what makes primes the building blocks of all integers. It is also what makes factoring a well-defined problem with a single correct answer.

How RSA Encryption Actually Works

RSA was developed by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT. The system uses two keys: a public key for encryption and a private key for decryption. The mathematical mechanics rely on modular arithmetic and Euler's theorem.

The process works in defined steps:

• Choose two large random primes, p and q (each typically 1,024 bits or larger)
• Compute their product: n = p × q (this becomes part of the public key)
• Compute the totient: φ(n) = (p − 1)(q − 1)
• Choose a public exponent e (commonly 65,537) that is coprime to φ(n)
• Compute the private exponent d, the modular inverse of e mod φ(n)
• Public key: (n, e). Private key: d. Encryption: c = m^e mod n. Decryption: m = c^d mod n

The security rests on one fact: without knowing p and q, computing d from (n, e) requires factoring n. And factoring n, when p and q are each 1,024 bits (about 308 digits), is beyond current computational reach.

The Factoring Problem: Hard But Not Proven Impossible

No one has proven that factoring is inherently difficult. It has not been shown to be NP-hard. The best classical algorithm for factoring large numbers is the General Number Field Sieve (GNFS), which runs in sub-exponential but super-polynomial time. For a 2048-bit RSA key, the GNFS would require an estimated 2^112 operations—a number so large that even distributing the computation across every computer on Earth would not finish in a human lifetime.

But the difficulty is empirical, not proven. This is a subtle but important distinction. Cryptographers operate on the assumption that no efficient classical factoring algorithm exists, while acknowledging that assumption could be wrong.

• RSA-768 (232 digits) was factored in 2009 using the GNFS, requiring the equivalent of 2,000 years of single-core computation
• RSA-896 and larger challenge numbers remain unfactored
• Key sizes have grown over time: 512-bit RSA was standard in the 1990s; 2048-bit is the current minimum recommendation; 4096-bit is used for high-security applications
• Each doubling of key size increases factoring difficulty by roughly 2^30 to 2^40 operations

Beyond RSA: Diffie-Hellman and Elliptic Curves

RSA is not the only cryptosystem built on hard mathematical problems. The Diffie-Hellman key exchange, published in 1976 (one year before RSA), relies on the discrete logarithm problem: given g, p, and g^a mod p, finding a is computationally hard.

Elliptic Curve Cryptography (ECC), introduced by Neal Koblitz and Victor Miller independently in 1985, uses the discrete logarithm problem on elliptic curve groups. ECC achieves equivalent security to RSA with much smaller key sizes.

ECC's smaller keys mean faster computation, lower bandwidth, and less storage—advantages that matter for mobile devices, IoT sensors, and TLS handshakes. Modern HTTPS connections predominantly use ECC for key exchange.

The Quantum Threat: Shor's Algorithm

In 1994, mathematician Peter Shor developed a quantum algorithm that can factor integers in polynomial time. On a sufficiently large quantum computer, Shor's algorithm would break RSA-2048 in hours rather than billions of years. It would also break Diffie-Hellman and ECC with comparable ease.

The catch: "sufficiently large" means a fault-tolerant quantum computer with thousands of logical qubits. As of early 2025, the largest quantum computers have roughly 1,000 physical qubits, and the error rates are too high for running Shor's algorithm on cryptographically relevant numbers. Estimates vary, but most experts place the timeline for a cryptographically relevant quantum computer at 10 to 30 years.

• Shor's algorithm reduces factoring from sub-exponential to polynomial time—an exponential speedup
• Grover's algorithm, another quantum algorithm, speeds up brute-force search quadratically, effectively halving symmetric key security (AES-256 becomes AES-128 equivalent)
• The threat is not just future: adversaries may be recording encrypted traffic today for decryption later ("harvest now, decrypt later")
• This forward-looking threat is driving the urgency of the transition to post-quantum cryptography

Post-Quantum Cryptography: Preparing for the Shift

NIST (the U.S. National Institute of Standards and Technology) launched a post-quantum cryptography standardization process in 2016. After six years and three rounds of evaluation, NIST announced its first selections in July 2022.

The winning algorithms rely on mathematical problems believed to be hard for both classical and quantum computers:

• CRYSTALS-Kyber (now ML-KEM): A key encapsulation mechanism based on the Module Learning With Errors (MLWE) problem—a lattice-based problem
• CRYSTALS-Dilithium (now ML-DSA): A digital signature scheme, also lattice-based
• FALCON: A signature scheme using NTRU lattices, selected for applications needing compact signatures
• SPHINCS+: A hash-based signature scheme, included as a backup in case lattice-based assumptions prove wrong

The transition will take years. Every protocol that uses RSA, Diffie-Hellman, or ECC must be updated. TLS, SSH, VPNs, code signing, email encryption, blockchain—all are affected. Google, Cloudflare, and Apple have already begun testing hybrid schemes that combine classical and post-quantum algorithms during the transition period. The migration is the largest cryptographic infrastructure change since the adoption of public-key cryptography itself in the 1990s.