The Greatest Common Divisor Problem
The Greatest Common Divisor (GCD) of two integers is the largest integer that evenly divides both of them. Computing the GCD efficiently is a building block for numerous algorithms, including simplifying fractions and the RSA cryptography discussed later in this article.
Euclid's Algorithm
The ancient Euclidean Algorithm computes the GCD using a remarkably simple recursive insight: the GCD of two numbers does not change if the larger number is replaced by its remainder when divided by the smaller one.
EUCLID(a, b):
if b == 0:
return a
return EUCLID(b, a mod b)Tracing through an example demonstrates the elegant simplicity of the reduction:
EUCLID(48, 18):
48 mod 18 = 12 → EUCLID(18, 12)
18 mod 12 = 6 → EUCLID(12, 6)
12 mod 6 = 0 → EUCLID(6, 0)
b == 0, return 6
GCD(48, 18) = 6Why the Algorithm Terminates Quickly
A classic theorem states that Euclid's algorithm runs in O(log(min(a, b))) time — remarkably fast even for very large numbers. This can be proven by showing that after two recursive calls, the smaller argument at least halves, which relates to a deeper connection with Fibonacci numbers: the worst-case input for Euclid's algorithm (requiring the most steps relative to the input size) is a pair of consecutive Fibonacci numbers.
The Extended Euclidean Algorithm
The Extended Euclidean Algorithm computes not only the GCD, but also integer coefficients x and y satisfying Bézout's identity: ax + by = gcd(a, b). This extension is essential for computing Modular Multiplicative Inverses, a critical building block for the RSA algorithm discussed later in this article.
EXTENDED-EUCLID(a, b):
if b == 0:
return (a, 1, 0)
(d, x', y') = EXTENDED-EUCLID(b, a mod b)
(d, x, y) = (d, y', x' - ⌊a/b⌋ · y')
return (d, x, y)Fast Modular Exponentiation
Many cryptographic algorithms require computing aᵇ mod n where b may be an enormous number, potentially hundreds of digits long. Computing this the naive way — multiplying a by itself b times — would be catastrophically slow for such large exponents. The Repeated Squaring technique solves this dramatically faster.
MODULAR-EXPONENTIATION(a, b, n):
result = 1
a = a mod n
while b > 0:
if b is odd:
result = (result · a) mod n
b = b >> 1 // integer divide by 2
a = (a · a) mod n // square a for the next bit
return resultThis algorithm exploits the binary representation of the exponent, discussed earlier in this series regarding number representation: instead of multiplying by a a total of b times, it squares a running value once per bit of b, and multiplies that squared value into the result only when the corresponding bit is set.
Example: computing 3^13 mod 7
13 in binary is 1101
result=1, a=3, b=13(1101): bit=1, result=3, a=9mod7=2
b=6(110): bit=0, a=4
b=3(11): bit=1, result=3·4mod7=5, a=16mod7=2
b=1(1): bit=1, result=5·2mod7=3, a=4
b=0: done
3^13 mod 7 = 3 (verify: 3^13 = 1594323, 1594323 mod 7 = 3 ✓)Since the number of iterations equals the number of bits in b, this algorithm runs in O(log b) multiplications, an exponential speedup compared to b naive multiplications — the difference between computing something instantly versus something that would take longer than the age of the universe for cryptographically sized numbers.
RSA: Public-Key Cryptography Built on These Primitives
The RSA Cryptosystem, one of the most widely used public-key encryption schemes, is built directly on the number-theoretic algorithms covered in this article, combined with the computational difficulty of factoring large numbers.
Key Generation
1. Choose two large, distinct prime numbers p and q
2. Compute n = p · q (the "modulus," made public)
3. Compute φ(n) = (p-1)(q-1) (Euler's totient function)
4. Choose a public exponent e, coprime to φ(n)
5. Compute the private exponent d, the modular inverse
of e modulo φ(n), using the Extended Euclidean
Algorithm covered earlier in this article:
d · e ≡ 1 (mod φ(n))
Public key: (n, e)
Private key: (n, d)Encryption and Decryption
To encrypt a message m (as a number less than n):
c = m^e mod n (using fast modular exponentiation)
To decrypt the ciphertext c:
m = c^d mod n (using fast modular exponentiation)The mathematics guaranteeing this scheme works correctly relies on Euler's Theorem, a generalization of a classical number theory result, which ensures that raising a number to the power ed modulo n returns the original number, since ed ≡ 1 (mod φ(n)) by construction.
Why RSA Is Considered Secure
The security of RSA rests on the assumption that Integer Factorization — finding p and q given only their product n — is computationally infeasible for sufficiently large primes (typically 1024 bits or more in modern practice), despite n itself being public. No efficient classical algorithm for factoring large integers is known, and this problem's difficulty (though not proven NP-complete, unlike the problems discussed earlier in this series) has resisted decades of attempted efficient solutions, providing the practical security foundation for the entire scheme.
Without knowing p and q individually, an attacker
cannot compute φ(n), and therefore cannot compute
the private key d, even with full knowledge of the
public key (n, e)Why This Combination of Simple Algorithms Secures the Internet
It is a remarkable fact that the security underlying much of modern digital communication — HTTPS connections, digital signatures, secure email — rests on the combination of a handful of elegant, centuries-to-decades-old number-theoretic algorithms covered in this article: Euclid's ancient GCD algorithm, the extended version for computing modular inverses, fast modular exponentiation for practical computation with enormous numbers, and the presumed hardness of integer factorization. This is a fitting conclusion for a series exploring algorithms throughout computer science: even one of the most consequential real-world applications of algorithmic thinking is built from surprisingly simple, well-understood mathematical building blocks, each individually explainable, combined into something far more powerful than any single piece alone.