How Number Theory Supports Cryptography

Cryptography is much broader than prime numbers, but elementary number theory provides a clear doorway into several important ideas: remainders, inverses, prime factorization, and operations that are easier to perform than to reverse.

Modular arithmetic keeps only the remainder

Writing a mod n means the remainder after division by n. On a 12-hour clock, 10 plus 5 hours lands at 3, so 10 + 5 = 3 mod 12.

Worked example: 29 mod 7 = 1 because 29 = 4 x 7 + 1. This lets a large calculation be reduced after every step: 29^2 mod 7 is the same as 1^2 mod 7, so the remainder is 1.

Cryptographic algorithms use modular operations at a scale and in a structure far beyond a clock example, but the remainder rule is the same.

Primes and greatest common divisors control inverses

An integer a has a multiplicative inverse modulo n only when gcd(a, n) = 1.

Worked example: Modulo 10, 3 has inverse 7 because 3 x 7 = 21, and 21 mod 10 = 1. The number 4 has no inverse modulo 10 because gcd(4, 10) = 2.

The Euclidean algorithm finds a greatest common divisor without listing every factor. For 126 and 84: 126 = 1 x 84 + 42, then 84 = 2 x 42, so the GCD is 42.

RSA as a small, classic example

NIST describes RSA as a public-key algorithm used for purposes such as key establishment and digital signatures. Its real use requires large parameters, standardized encoding, careful implementation, and expert-reviewed libraries. The tiny example below is deliberately insecure and only shows the number theory.

Choose primes p = 5 and q = 11, giving n = 55 and phi(n) = 4 x 10 = 40. Choose e = 3, which is coprime to 40. Its inverse modulo 40 is d = 27 because 3 x 27 = 81, and 81 mod 40 = 1.

For message m = 7, the toy encryption step gives c = 7^3 mod 55 = 13. Repeated squaring can verify the reverse step 13^27 mod 55 = 7 without expanding the full power:

• 13^2 mod 55 = 4
• 13^8 mod 55 = 36
• 13^16 mod 55 = 31
• Since 27 = 16 + 8 + 2 + 1, reduce 31 x 36 x 4 x 13 mod 55 to get 7.

Never build a real security feature from this example. "Textbook RSA" without the required standards and protections is not a secure design.

The modern landscape is larger

RSA is not a synonym for cryptography. Modern systems also use symmetric ciphers, hashes, elliptic-curve methods, authenticated encryption, and post-quantum algorithms. In 2024, NIST approved its first three post-quantum cryptography standards, based on lattice and hash constructions rather than integer factorization.

That does not make elementary number theory obsolete. It makes the lesson more precise: different security constructions rely on different mathematical problems, assumptions, and implementation rules.

Practice the foundations

1. Find 83 mod 9 and verify it with a digit-sum check.
2. Use the Euclidean algorithm to find gcd(84, 126).
3. Find an inverse of 5 modulo 12.
4. Test whether 97 has a prime factor no larger than its square root.

The goal is not to design encryption by hand. It is to see how familiar arithmetic becomes a language for reasoning about one-way operations and reversible transformations.