Difficulty: Intermediate | Prerequisites: Basic number theory, familiarity with RSA key generation
RSA works because of a handful of properties from modular arithmetic and number theory. The modular inverse lets you compute the private key from the public key (during generation only), and Fermat's Little Theorem provides the proof that encrypting then decrypting always gives back the original message. If you understand these two ideas, the entire RSA pipeline makes sense.
Modular arithmetic
Arithmetic where numbers "wrap around" after reaching a fixed value (the modulus). 17 mod 5 = 2 because 17 divided by 5 leaves remainder 2. Think of it as clock arithmetic: 15:00 on a 12-hour clock reads as 3.
Congruence (≡)
a ≡ b (mod N) means a and b leave the same remainder when divided by N. In simple terms, a and b are "the same" within the mod-N number system.
Coprime (relatively prime)
Two integers are coprime if their greatest common divisor (GCD) is 1. For example, 7 and 10 are coprime because they share no factor other than 1. In RSA, e and φ(N) must be coprime.
Greatest common divisor (GCD)
The largest positive integer that divides both a and b. gcd(12, 8) = 4. When gcd(a, b) = 1, the numbers are coprime.
Modular inverse
b is the modular inverse of a modulo N if (a × b) mod N = 1. Think of it as "division" in modular arithmetic: you cannot divide, but you can multiply by the inverse to achieve the same effect.
Fermat's Little Theorem
If p is prime and m is not divisible by p, then m^(p−1) ≡ 1 (mod p). In simple terms, raising any non-multiple of p to the power (p − 1) always produces a remainder of 1 when divided by p.
Extended Euclidean algorithm
An algorithm that, given a and N, finds integers x and y such that a × x + N × y = gcd(a, N). When gcd = 1, x is the modular inverse of a mod N. This is the standard method for computing d in RSA key generation.
Euler's theorem (generalisation of Fermat's)
For any a coprime to N: a^φ(N) ≡ 1 (mod N). Fermat's Little Theorem is the special case where N is prime. This theorem is what ultimately proves RSA decryption works.
The modular inverse is the central operation that makes RSA key generation possible. Without it, there is no way to compute d from e.
Definition
b is the inverse of a modulo N if:
(a × b) mod N = 1
Equivalently, a × b ≡ 1 (mod N).
An inverse exists if and only if gcd(a, N) = 1 (i.e., a and N are coprime).
Worked example 1: Inverse of 25 modulo 11
We need b such that 25 × b ≡ 1 (mod 11).
Try b = 4: 25 × 4 = 100. 100 mod 11 = 100 − 9 × 11 = 100 − 99 = 1.
So the inverse of 25 mod 11 is 4.
Worked example 2: Inverse of 3 modulo 7
We need b such that 3 × b ≡ 1 (mod 7).
Try b = 5: 3 × 5 = 15. 15 mod 7 = 15 − 2 × 7 = 1.
So the inverse of 3 mod 7 is 5.
How this connects to RSA
During key generation, d is the inverse of e modulo φ(N). The extended Euclidean algorithm computes this efficiently even when the numbers are hundreds of digits long.
Fermat's Little Theorem is one of the mathematical results that guarantees RSA decryption recovers the original message.
Statement
If p is a prime number and m is any integer not divisible by p, then:
m^(p−1) ≡ 1 (mod p)
Equivalently: m^p ≡ m (mod p) for any integer m (this version holds even when p divides m).
Worked example
Verify for p = 7 and m = 4:
The theorem says 4^(7−1) = 4^6 ≡ 1 (mod 7).
4^6 = 4096. 4096 mod 7: 4096 / 7 = 585 remainder 1. So 4096 mod 7 = 1.
Confirmed.
Why it matters for RSA
Euler's theorem generalises Fermat's result to composite moduli: a^φ(N) ≡ 1 (mod N) when gcd(a, N) = 1. Since e × d = 1 + k × φ(N) for some integer k, we get:
m^(e×d) = m^(1 + k×φ(N)) = m × (m^φ(N))^k ≡ m × 1^k = m (mod N)
This is the proof that decryption works: raising the ciphertext to the power d undoes the encryption exponent e, giving back the original m.
The extended Euclidean algorithm is the standard method for computing modular inverses in practice.
What it does
Given integers a and N, it finds integers x and y such that:
a × x + N × y = gcd(a, N)
When gcd(a, N) = 1, x is the modular inverse of a modulo N.
Sketch of the procedure
Apply the standard Euclidean algorithm to find gcd(a, N) by repeated division.
Work backwards through the division steps, expressing each remainder as a linear combination of a and N.
The coefficient of a in the final expression is x, the modular inverse (reduce it mod N if negative).
Brief example: Find the inverse of 7 mod 1740
This is the computation from the RSA key generation example (finding d when e = 7, φ(N) = 1740).
Apply Euclidean algorithm: 1740 = 248 × 7 + 4, then 7 = 1 × 4 + 3, then 4 = 1 × 3 + 1, then 3 = 3 × 1 + 0. gcd = 1.
Back-substitute to express 1 as a combination of 7 and 1740.
The result gives d = 1243 (after reducing mod 1740).
The full back-substitution is mechanical but tedious to show in compact form. In exams, you may be given smaller numbers or asked to verify a given inverse rather than derive one from scratch.
Exercise 1: Compute the inverse of 3 modulo 7
Find b such that 3 × b ≡ 1 (mod 7).
3 × 5 = 15. 15 mod 7 = 1.
Answer: b = 5.
Exercise 2: Verify Fermat's Little Theorem for p = 7, m = 4
4^(7−1) = 4^6 = 4096.
4096 mod 7 = 1.
Confirmed: m^(p−1) ≡ 1 (mod p).
Exercise 3: Encrypt and decrypt "STOP" with RSA
Public key: (N, e) = (2537, 13). Private key: d = 937.
Encryption:
Map letters: S = 19, T = 20, O = 15, P = 16.
Form blocks: m₁ = 1819, m₂ = 1415.
c₁ = 1819^13 mod 2537 = 2081.
c₂ = 1415^13 mod 2537 = 2182.
Ciphertext: (2081, 2182).
Decryption:
m₁ = 2081^937 mod 2537 = 1819.
m₂ = 2182^937 mod 2537 = 1415.
Convert back: 18,19 → S,T and 14,15 → O,P → "STOP".
Formula | Statement | When it applies |
|---|---|---|
Modular inverse | a × b ≡ 1 (mod N) | gcd(a, N) = 1 |
Fermat's Little Theorem | m^(p−1) ≡ 1 (mod p) | p is prime, p does not divide m |
Euler's theorem | a^φ(N) ≡ 1 (mod N) | gcd(a, N) = 1 |
RSA correctness | m^(e×d) ≡ m (mod N) | Follows from Euler's theorem and e×d ≡ 1 (mod φ(N)) |
Extended Euclidean | a×x + N×y = gcd(a, N) | Always; x = inverse when gcd = 1 |
Students sometimes think every number has a modular inverse. It does not. The inverse of a mod N exists only when gcd(a, N) = 1. If they share a common factor, no inverse exists.
A frequent mistake is applying Fermat's Little Theorem when p is not prime. The theorem requires p to be prime. For composite moduli, use Euler's theorem instead.
Students sometimes confuse Fermat's Little Theorem (m^(p−1) ≡ 1 mod p) with the alternative form (m^p ≡ m mod p). Both are correct, but the second form works even when p divides m, while the first form requires p not to divide m.
When computing modular inverses by trial, students sometimes forget to reduce the result modulo N. The inverse should always be expressed as a number between 0 and N − 1.
⚠️ Computing modular inverses by hand is a near-certain exam question. Practise both trial-and-error (for small numbers) and the extended Euclidean algorithm (for larger ones).
⚠️ You may be asked to state Fermat's Little Theorem and verify it for given values. Know both forms.
⚠️ Understanding why RSA decryption works requires Euler's theorem. Be prepared to sketch the proof chain: e × d ≡ 1 (mod φ(N)) → m^(e×d) = m^(1+kφ(N)) → m × (m^φ(N))^k ≡ m (mod N).
⚠️ The condition gcd(a, N) = 1 for the existence of a modular inverse is frequently tested as a true/false or short-answer question.
True or false: The inverse of 6 modulo 9 exists. (False. gcd(6, 9) = 3 ≠ 1.)
Fill in the blank: Fermat's Little Theorem states that m^(___) ≡ 1 (mod p) when p is prime and p does not divide m. (p − 1)
True or false: 4^6 mod 7 = 1. (True. By Fermat's Little Theorem with p = 7.)
Fill in the blank: The extended Euclidean algorithm finds x and y such that a × x + N × y = ___. (gcd(a, N))
True or false: Euler's theorem is a special case of Fermat's Little Theorem. (False. It is the other way round. Fermat's is the special case of Euler's.)
Q: Find the modular inverse of 5 modulo 12.
A: We need b such that 5 × b ≡ 1 (mod 12). 5 × 5 = 25, and 25 mod 12 = 1. So the inverse is 5.
Q: Does the inverse of 4 modulo 8 exist? Explain.
A: No. gcd(4, 8) = 4 ≠ 1, so no inverse exists.
Q: Using Fermat's Little Theorem, compute 3^10 mod 11.
A: Since 11 is prime and 11 does not divide 3, Fermat tells us 3^10 ≡ 1 (mod 11). The answer is 1.
Q: Explain in one or two sentences why m^(e×d) mod N = m in RSA.
A: Because e × d ≡ 1 (mod φ(N)), we can write e × d = 1 + k × φ(N). By Euler's theorem, m^φ(N) ≡ 1 (mod N), so m^(e×d) = m × (m^φ(N))^k ≡ m × 1 = m (mod N).
Q: Compute gcd(7, 1740) and state what this tells you about choosing e = 7 for RSA with φ(N) = 1740.
A: 1740 = 248 × 7 + 4, then 7 = 1 × 4 + 3, then 4 = 1 × 3 + 1, then 3 = 3 × 1 + 0. gcd = 1. Since gcd(7, 1740) = 1, e = 7 is a valid encryption exponent.
Modular arithmetic underpins not just RSA but all of public-key cryptography, including Diffie-Hellman key exchange and elliptic curve cryptography. Fermat's Little Theorem is a stepping stone to more general results in abstract algebra (group theory), where it becomes a statement about the order of elements in a finite group. The extended Euclidean algorithm also appears in coding theory and solving linear Diophantine equations.
modular arithmetic, modular inverse, multiplicative inverse mod N, Fermat's Little Theorem, Euler's theorem, Euler's totient function, extended Euclidean algorithm, GCD, greatest common divisor, coprime, relatively prime, congruence, RSA proof, RSA correctness, number theory, CS 182, Foundations of Computer Science, Purdue