CryptoChronicles

Number Theory Meets Cryptography

September 12, 2025 • by Alex Miller

Number theory provides the mathematical foundation for many modern cryptographic schemes. From prime numbers to modular arithmetic, these concepts enable secure communication across the internet.

Prime Numbers & Their Role

Prime numbers are central to RSA, Diffie‑Hellman, and many other protocols. The difficulty of factoring large composites into their prime components forms the basis of RSA's security.

Modular Exponentiation

Efficient computation of a^b mod n is crucial. The square‑and‑multiply algorithm reduces the complexity dramatically.

function modExp(base, exp, mod) {
  let result = 1n;
  let b = BigInt(base);
  let e = BigInt(exp);
  let m = BigInt(mod);
  while (e > 0) {
    if (e & 1n) result = (result * b) % m;
    e >>= 1n;
    b = (b * b) % m;
  }
  return result;
}

RSA Overview

The RSA algorithm consists of three steps: key generation, encryption, and decryption.

Key generation involves picking two large primes p and q, computing n = p·q and the totient φ(n) = (p‑1)(q‑1). Choose an exponent e coprime with φ(n), then compute the modular inverse d of e modulo φ(n).

Encryption of a message m (as an integer) is performed as:

$$c \\equiv m^e \\pmod{n}$$

Decryption uses the private exponent d:

$$m \\equiv c^d \\pmod{n}$$

Interactive Demo

Enter small prime numbers to see RSA in action.