I think of number theory as the mathematical bedrock underneath nearly everything else in this series of files — the knapsack cryptosystem, discrete logarithms, prime generation, and factoring all lean on number-theoretic tools I want to isolate and explain properly here: the Euclidean algorithm, modular exponentiation, the Extended Euclidean algorithm, Euler’s theorem and totient function, and the Chinese Remainder Theorem. When I first started learning cryptography, I found that once these five or six core algorithms clicked for me, entire cryptosystems that had seemed like magic suddenly made complete algebraic sense. That’s what I want to recreate here: a focused walkthrough of the number-theoretic toolbox itself.
History and Background
I trace nearly all of these tools back over two thousand years. The Euclidean algorithm for computing the greatest common divisor appears in Euclid’s Elements (circa 300 BC) and is often cited as the oldest algorithm still in common use today. Fermat’s Little Theorem dates to the 17th century. Euler generalized it in the 18th century into what we now call Euler’s theorem, along with defining the Euler totient function that bears his name. The Chinese Remainder Theorem traces back even further, to the Chinese mathematician Sun Tzu (the mathematician, not the military strategist) in the 3rd to 5th century AD, originally posed as a puzzle about counting soldiers. What I find remarkable is that these tools sat as “pure” mathematics — elegant but without obvious practical urgency — for centuries, until the 1970s public-key cryptography revolution (RSA, Diffie-Hellman) suddenly made them absolutely central to real-world computer security.
Problem Statement
The number-theoretic algorithms I cover here solve a cluster of closely related problems: finding the greatest common divisor of two integers efficiently; finding modular inverses (the “division” operation in modular arithmetic); computing large modular exponentiations efficiently (essential for RSA and Diffie-Hellman); counting integers coprime to a given number (Euler’s totient function, essential for RSA key generation); and solving systems of simultaneous modular congruences (the Chinese Remainder Theorem, used both to speed up RSA decryption and in some cryptanalytic attacks). Each of these, on its own, would be a minor curiosity; together, they form the operational core of modern public-key cryptography.
Core Concepts
- Greatest common divisor (GCD) – the largest integer dividing two given integers without remainder; computed efficiently via the Euclidean algorithm.
- Extended Euclidean algorithm – an extension of the Euclidean algorithm that, alongside the GCD, also computes the Bézout coefficients $x, y$ satisfying $ax + by = \gcd(a,b)$, which directly gives modular inverses.
- Modular inverse – for $a$ coprime to $m$, the value $a^{-1}$ such that $a \cdot a^{-1} \equiv 1 \pmod m$; the modular equivalent of division.
- Modular exponentiation (square-and-multiply) – computing $a^b \bmod m$ efficiently in $O(\log b)$ multiplications rather than $O(b)$.
- Euler’s totient function $\varphi(n)$ – counts the integers in $[1, n]$ coprime to $n$; for $n = pq$ (product of two distinct primes), $\varphi(n) = (p-1)(q-1)$, which is exactly the quantity RSA key generation depends on.
- Euler’s theorem – generalizes Fermat’s Little Theorem: for $a$ coprime to $n$, $a^{\varphi(n)} \equiv 1 \pmod n$.
- Chinese Remainder Theorem (CRT) – guarantees a unique solution modulo the product of pairwise coprime moduli to a system of simultaneous congruences, and gives a constructive algorithm for finding it.
How It Works
I’ll walk through each core algorithm’s mechanics briefly:
Euclidean algorithm (GCD):
- Given integers $a$ and $b$ (with $a \ge b > 0$), I repeatedly replace $(a, b)$ with $(b, a \bmod b)$.
- I continue until $b = 0$; at that point, $a$ is the GCD.
Extended Euclidean algorithm:
- I run the same division steps as the standard Euclidean algorithm, but I additionally track coefficients that express each remainder as a linear combination of the original $a$ and $b$.
- By the time I reach the final nonzero remainder (the GCD), I’ve also computed $x$ and $y$ such that $ax + by = \gcd(a,b)$.
- If $\gcd(a,m) = 1$, the coefficient $x$ (reduced modulo $m$) is exactly the modular inverse $a^{-1} \bmod m$.
Modular exponentiation (square-and-multiply):
- I write the exponent $b$ in binary.
- I process the bits from most significant to least significant, squaring a running result at each step, and multiplying in the base whenever the current bit is 1.
- This computes $a^b \bmod m$ using only $O(\log b)$ modular multiplications instead of $b – 1$.
Chinese Remainder Theorem:
- Given congruences $x \equiv a_1 \pmod{m_1}$, $x \equiv a_2 \pmod{m_2}$, …, with pairwise coprime moduli, I compute $M = m_1 m_2 \cdots m_k$.
- For each $i$, I compute $M_i = M / m_i$ and its modular inverse $y_i = M_i^{-1} \bmod m_i$ (via the Extended Euclidean algorithm).
- The unique solution modulo $M$ is $x \equiv \sum_i a_i M_i y_i \pmod M$.
Working Principle
I think the deep unifying idea behind all of these algorithms is that modular arithmetic behaves like ordinary arithmetic in most respects (it forms a ring, and when the modulus is prime, a field), but with the crucial difference that “division” only works for numbers coprime to the modulus, and that inverse must be constructed rather than computed directly — this is exactly what the Extended Euclidean algorithm provides. Euler’s theorem tells me that exponentiation “wraps around” with a period related to $\varphi(n)$, which is what lets RSA’s encryption/decryption exponents be chosen as multiplicative inverses of each other modulo $\varphi(n)$ rather than modulo $n$ itself — a subtle but essential distinction. The Chinese Remainder Theorem, meanwhile, exploits the fact that working modulo a composite number with coprime factors is mathematically equivalent to working independently modulo each factor and recombining — this isomorphism (formally, $\mathbb{Z}{m_1 m_2} \cong \mathbb{Z}{m_1} \times \mathbb{Z}_{m_2}$) both accelerates RSA decryption (by doing smaller computations modulo $p$ and $q$ separately instead of one large computation modulo $n$) and, when implemented carelessly, opens the door to certain fault-injection cryptanalytic attacks.
Mathematical Foundation
Euclidean algorithm identity:
$$\gcd(a, b) = \gcd(b, a \bmod b), \qquad \gcd(a, 0) = a$$
Bézout’s identity (from the Extended Euclidean algorithm):
$$ax + by = \gcd(a, b) \text{ for some integers } x, y$$
Modular inverse (when $\gcd(a,m)=1$):
$$a \cdot a^{-1} \equiv 1 \pmod{m}$$
Fast modular exponentiation, writing $b$ in binary as $b = \sum_i b_i 2^i$:
$$a^b = \prod_{i : b_i = 1} a^{2^i} \pmod m$$
computed via repeated squaring in $O(\log b)$ steps.
Euler’s totient function, for $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$:
$$\varphi(n) = n \prod_{i=1}^{k} \left(1 – \frac{1}{p_i}\right)$$
For $n = pq$ with $p, q$ distinct primes:
$$\varphi(n) = (p-1)(q-1)$$
Euler’s theorem:
$$a^{\varphi(n)} \equiv 1 \pmod n \quad \text{for } \gcd(a,n)=1$$
Chinese Remainder Theorem reconstruction, given $x \equiv a_i \pmod{m_i}$ for pairwise coprime $m_i$, with $M = \prod m_i$, $M_i = M/m_i$, and $y_i = M_i^{-1} \bmod m_i$:
$$x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod M$$
RSA’s use of these tools together: choosing primes $p, q$, computing $n = pq$ and $\varphi(n) = (p-1)(q-1)$, choosing public exponent $e$ coprime to $\varphi(n)$, and computing private exponent $d = e^{-1} \bmod \varphi(n)$ via the Extended Euclidean algorithm — encryption is $c = m^e \bmod n$ (fast modular exponentiation), and decryption is $m = c^d \bmod n$, which works precisely because of Euler’s theorem: $c^d = m^{ed} = m^{1 + k\varphi(n)} = m \cdot (m^{\varphi(n)})^k \equiv m \cdot 1^k = m \pmod n$.
Diagrams
flowchart TD
A[Choose primes p, q] --> B[Compute n = p*q]
B --> C[Compute phi_n = p-1 * q-1]
C --> D[Choose e coprime to phi_n]
D --> E[Extended Euclidean: compute d = e^-1 mod phi_n]
E --> F[Public key: n, e Private key: d]
F --> G[Encrypt: c = m^e mod n via fast exponentiation]
G --> H[Decrypt: m = c^d mod n via Euler theorem]Pseudocode
// Extended Euclidean Algorithm: returns (gcd, x, y) such that a*x + b*y = gcd
function extended_gcd(a, b):
if b == 0:
return (a, 1, 0)
gcd, x1, y1 = extended_gcd(b, a mod b)
x = y1
y = x1 - (a div b) * y1
return (gcd, x, y)
function mod_inverse(a, m):
gcd, x, _ = extended_gcd(a, m)
if gcd != 1:
error("no inverse exists")
return ((x mod m) + m) mod m
// Fast modular exponentiation (square-and-multiply)
function pow_mod(base, exp, mod):
result = 1
base = base mod mod
while exp > 0:
if exp is odd:
result = (result * base) mod mod
base = (base * base) mod mod
exp = exp div 2
return result
// Euler's totient for n = p*q
function totient_of_semiprime(p, q):
return (p - 1) * (q - 1)
// Chinese Remainder Theorem
function crt(remainders[], moduli[]):
M = product(moduli)
x = 0
for i in 0..len(moduli)-1:
Mi = M / moduli[i]
yi = mod_inverse(Mi, moduli[i])
x = x + remainders[i] * Mi * yi
return x mod M
Step-by-Step Example
I’ll build a small full RSA-style example using all these tools together.
- I choose primes
p = 61andq = 53. n = p*q = 61*53 = 3233.phi(n) = (p-1)(q-1) = 60*52 = 3120.- I choose public exponent
e = 17(I checkgcd(17, 3120) = 1, which holds since 17 is prime and doesn’t divide 3120). - I compute
d = e^-1 mod 3120using the Extended Euclidean algorithm. Running the algorithm:3120 = 183*17 + 9,17 = 1*9 + 8,9 = 1*8 + 1,8 = 8*1 + 0. Back-substituting:1 = 9 - 1*8 = 9 - 1*(17-1*9) = 2*9 - 1*17 = 2*(3120-183*17) - 1*17 = 2*3120 - 367*17. Sox = -367for the17coefficient. Reducing modulo 3120:-367 mod 3120 = 2753. Sod = 2753. - Verification:
17 * 2753 = 46801.46801 / 3120 = 15.0003...,15*3120=46800, remainder1. Confirmed:17*2753 ≡ 1 (mod 3120). - Public key:
(n=3233, e=17). Private key:d=2753. - To encrypt message
m = 65:c = 65^17 mod 3233. Using fast modular exponentiation (square-and-multiply), this evaluates toc = 2790. - To decrypt:
m = 2790^2753 mod 3233. Using fast modular exponentiation again, this evaluates back tom = 65, matching the original plaintext exactly — demonstrating Euler’s theorem in action.
Time Complexity
- Euclidean algorithm: $O(\log(\min(a,b)))$ division steps, one of the fastest classical algorithms relative to input size, thanks to the rapid shrinkage guaranteed by the Fibonacci-related worst-case analysis.
- Extended Euclidean algorithm: same asymptotic complexity as the standard Euclidean algorithm, $O(\log(\min(a,b)))$, since it performs identical division steps plus $O(1)$ extra bookkeeping per step.
- Fast modular exponentiation: $O(\log b)$ modular multiplications for exponent $b$, each multiplication costing $O(k^2)$ for $k$-bit numbers using schoolbook multiplication (or faster with advanced multiplication algorithms), giving overall $O(k^2 \log b)$ for typical RSA-scale operations.
- Euler’s totient (for a known factorization): $O(\log n)$ given the prime factorization, since it’s a simple product formula; computing $\varphi(n)$ without knowing the factorization is exactly as hard as factoring $n$ itself, which is precisely why RSA’s security holds even though $\varphi(n)$ is what an attacker would ultimately want.
- Chinese Remainder Theorem: $O(k \log M)$ for $k$ congruences with combined modulus $M$, dominated by the modular inverse computations for each modulus.
Space Complexity
All of these algorithms require only $O(\log n)$ space (proportional to the bit-length of the numbers involved) to store intermediate values, coefficients, and results — none of them require storage proportional to the numeric value of $n$ itself, which is what makes them practical even for the enormous numbers (hundreds of digits) used in real RSA and Diffie-Hellman implementations.
Correctness Analysis
I verify the Euclidean algorithm’s correctness via the identity $\gcd(a,b) = \gcd(b, a \bmod b)$, which follows because any common divisor of $a$ and $b$ must also divide $a \bmod b = a – qb$, and conversely; since the second argument strictly decreases each step and is bounded below by zero, the algorithm terminates, and it terminates precisely at the GCD by this invariant. The Extended Euclidean algorithm’s correctness follows by induction on the same recursive structure, tracking that at every step, the current remainder can indeed be expressed as an integer linear combination of the original $a$ and $b$ — this invariant is preserved by the back-substitution at each level of the recursion. Euler’s theorem’s correctness is a consequence of Lagrange’s theorem from group theory: the multiplicative group of integers coprime to $n$ has order $\varphi(n)$, so by Lagrange’s theorem, every element’s order divides $\varphi(n)$, meaning raising any such element to the $\varphi(n)$ power returns the identity (1). The Chinese Remainder Theorem’s correctness follows from verifying that the constructed $x = \sum a_i M_i y_i$ indeed satisfies each congruence individually (since $M_i \equiv 0 \pmod{m_j}$ for $j \ne i$, only the $i$-th term survives modulo $m_i$, and $M_i y_i \equiv 1 \pmod{m_i}$ by construction, so $x \equiv a_i \pmod{m_i}$), plus the ring isomorphism guarantee that this solution is unique modulo $M$.
Advantages
- These algorithms are extremely efficient, running in time polynomial (often near-linear) in the bit-length of the numbers involved, which is essential given that cryptographic numbers can be thousands of bits long.
- They compose cleanly: RSA, Diffie-Hellman, ElGamal, and DSA all reuse the exact same small toolbox (GCD, modular inverse, modular exponentiation, CRT), so mastering these few algorithms unlocks understanding of a huge swath of public-key cryptography.
- The Chinese Remainder Theorem in particular offers a genuine performance benefit in practice (roughly a 4x speedup for RSA decryption/signing when implemented with CRT), not just theoretical elegance.
Disadvantages
- Naive implementations of modular exponentiation (without square-and-multiply) are catastrophically slow for cryptographic-sized exponents, so correct algorithmic choice really matters, not just correct mathematics.
- CRT-based RSA implementations, while faster, are more vulnerable to certain fault-injection attacks (like the Bellcore attack), where inducing a computational error during one of the two smaller CRT sub-computations can leak the private key — so the performance benefit comes with an added implementation-security burden.
- Computing $\varphi(n)$ directly for an arbitrary large $n$ (without knowing its factorization) is exactly as hard as factoring, which is a feature for RSA’s security but a genuine practical limitation if I ever need the totient without already knowing the prime factors.
Applications
These number-theoretic algorithms underlie RSA key generation, encryption, and decryption; Diffie-Hellman and ElGamal’s modular exponentiation operations; CRT-based speedups for RSA private-key operations in essentially every major cryptographic library; and various other cryptographic protocols relying on modular arithmetic, including some secret-sharing schemes (which use CRT-like reconstruction) and zero-knowledge proof systems. Beyond cryptography, these same algorithms appear throughout computer algebra systems, coding theory (error-correcting codes), and general computational number theory research.
Implementation in C
#include <stdio.h>
#include <stdint.h>
/* Extended Euclidean algorithm: computes gcd and Bezout coefficients */
int64_t extended_gcd(int64_t a, int64_t b, int64_t *x, int64_t *y) {
if (b == 0) {
*x = 1;
*y = 0;
return a;
}
int64_t x1, y1;
int64_t gcd = extended_gcd(b, a % b, &x1, &y1);
*x = y1;
*y = x1 - (a / b) * y1;
return gcd;
}
int64_t mod_inverse(int64_t a, int64_t m) {
int64_t x, y;
int64_t g = extended_gcd(a, m, &x, &y);
if (g != 1) {
printf("No modular inverse exists\n");
return -1;
}
return ((x % m) + m) % m;
}
/* fast modular exponentiation */
uint64_t pow_mod(uint64_t base, uint64_t exp, uint64_t mod) {
uint64_t result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) result = (uint64_t)(( (__uint128_t)result * base) % mod);
base = (uint64_t)(( (__uint128_t)base * base) % mod);
exp >>= 1;
}
return result;
}
int main(void) {
/* Demonstrate a full small RSA example */
int64_t p = 61, q = 53;
int64_t n = p * q;
int64_t phi = (p - 1) * (q - 1);
int64_t e = 17;
int64_t d = mod_inverse(e, phi);
printf("p=%lld q=%lld n=%lld phi(n)=%lld\n", p, q, n, phi);
printf("Public exponent e=%lld\n", e);
printf("Private exponent d=%lld\n", d);
uint64_t message = 65;
uint64_t cipher = pow_mod(message, (uint64_t)e, (uint64_t)n);
uint64_t decrypted = pow_mod(cipher, (uint64_t)d, (uint64_t)n);
printf("Message: %llu\n", (unsigned long long)message);
printf("Encrypted: %llu\n", (unsigned long long)cipher);
printf("Decrypted: %llu\n", (unsigned long long)decrypted);
return 0;
}
Sample Input and Output
Input: the classic textbook RSA example with p=61, q=53, e=17, message m=65.
Output:
p=61 q=53 n=3233 phi(n)=3120
Public exponent e=17
Private exponent d=2753
Message: 65
Encrypted: 2790
Decrypted: 65
This matches my hand-worked example exactly, and the successful Decrypted: 65 confirms Euler’s theorem doing its job correctly.
Optimization Techniques
- Using iterative rather than recursive implementations of the Extended Euclidean algorithm avoids call-stack overhead for very large numbers.
- Precomputing CRT parameters (
d mod (p-1),d mod (q-1), andq^-1 mod p) once during RSA key generation, then using them for every subsequent decryption, is standard practice and yields roughly a 4x speedup over direct modular exponentiation with the full modulus $n$. - Using windowed or sliding-window variants of square-and-multiply (processing several exponent bits at a time rather than one) reduces the number of multiplications further, at the cost of small precomputed lookup tables.
- Using Montgomery multiplication for the repeated modular multiplications in exponentiation avoids expensive division operations, which is a major real-world performance technique in cryptographic libraries.
Common Mistakes
- Implementing modular exponentiation naively (via repeated multiplication without squaring) for cryptographic-sized exponents, resulting in impractically slow performance.
- Forgetting to reduce the result of the Extended Euclidean algorithm’s coefficient into the proper range $[0, m)$ before using it as a modular inverse (Bézout coefficients can come out negative).
- Confusing $\varphi(n)$ (Euler’s totient, based on $(p-1)(q-1)$) with $\lambda(n)$ (the Carmichael function, based on $\text{lcm}(p-1,q-1)$) — both work for RSA key generation, but they’re not the same value, and mixing them up in a from-scratch implementation can lead to subtle bugs.
- Implementing CRT-based RSA decryption without protecting against fault-injection attacks, which can leak the private key if an attacker can induce a computational fault during one of the sub-computations.
- Choosing a public exponent $e$ without verifying $\gcd(e, \varphi(n)) = 1$, which would make the modular inverse (and thus the private key $d$) impossible to compute.
Further Reading
- Rosen, K., Elementary Number Theory and Its Applications, Pearson: a standard textbook covering all the algorithms discussed here in depth.
- Rivest, R., Shamir, A., and Adleman, L., “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Communications of the ACM, 1978: https://people.csail.mit.edu/rivest/Rsapaper.pdf
- Menezes, van Oorschot, and Vanstone, Handbook of Applied Cryptography, Chapter 2 (Mathematical Background): https://cacr.uwaterloo.ca/hac/about/chap2.pdf
- Knuth, D., The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Addison-Wesley — the classical reference for the Euclidean algorithm and related number-theoretic computation.
- NIST FIPS 186-5, Digital Signature Standard: https://csrc.nist.gov/pubs/fips/186-5/final
