Difficulty: Intermediate | Prerequisites: Modular arithmetic basics, probability fundamentals
This material covers the number theory behind public-key cryptography: Fermat's Little Theorem for modular exponentiation, generators of multiplicative groups, the Diffie-Hellman key exchange protocol, and RSA encryption. A separate section covers group testing probability, which uses indicator random variables and linearity of expectation.
Fermat's Little Theorem
For any prime p and any a ∈ Z*_p, we have a^(p-1) ≡ 1 (mod p). Equivalently, for any integers a and k, a^(k(p-1)) ≡ 1 (mod p) when gcd(a, p) = 1. Think of it as: raising a number to the power (p - 1) modulo a prime always gives 1.
Z_p (multiplicative group modulo p)*
The set {1, 2, ..., p - 1} under multiplication modulo p, where p is prime. This group has p - 1 elements.
Generator of Z_p*
An element g ∈ Z*_p such that the set {g^1, g^2, ..., g^(p-1)} mod p produces every element of Z*_p. In simple terms, you can reach every number in the group by taking successive powers of g.
Diffie-Hellman key exchange
A protocol that allows two parties (Alice and Bob) to agree on a shared secret key over an insecure channel, using modular exponentiation. Neither party reveals their secret exponent.
RSA (Rivest-Shamir-Adleman)
A public-key cryptosystem. The public key is (n, e) and the private key is d, where n = pq for two primes, and ed ≡ 1 (mod (p-1)(q-1)). Encryption: c = m^e mod n. Decryption: m = c^d mod n.
Group testing
A technique for identifying affected individuals in a population by pooling samples and testing groups rather than individuals. Reduces the total number of tests required.
Fermat's Little Theorem says that for any prime p and any a ∈ Z*_p:
a^(p-1) ≡ 1 (mod p)
For any integers a and k: a^(k(p-1)) ≡ a (mod p).
Worked example: compute 3^2026 mod 11
Since 11 is prime, a^10 ≡ 1 (mod 11) for any a not divisible by 11. We have 3^2026 = 3^(10 · 202 + 6) = (3^10)^202 · 3^6 ≡ 1^202 · 3^6 (mod 11).
Now compute 3^6: 3^1 = 3, 3^2 = 9, 3^3 = 27 ≡ 5 (mod 11), 3^6 = (3^3)^2 = 5^2 = 25 ≡ 3 (mod 11). So 3^2026 ≡ 3 (mod 11).
The general technique: to compute a^N mod p, write N = q(p-1) + r using the division algorithm, then a^N ≡ a^r (mod p). This reduces a potentially enormous exponent to one that is at most p - 2.
A generator g of Z*_p is an element whose powers produce every element of the group. For Z*_p where p is prime, the group has p - 1 elements, so g is a generator if and only if {g^1 mod p, g^2 mod p, ..., g^(p-1) mod p} = {1, 2, ..., p - 1}.
Worked example: is g = 3 a generator of Z_11?*
Z*_11 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Compute the mod-p powers of g = 3:
3^1 = 3
3^2 = 9
3^3 = 27 ≡ 5 (mod 11)
3^4 ≡ 15 ≡ 4 (mod 11)
3^5 ≡ 12 ≡ 1 (mod 11)
We have cycled back to 3^5 ≡ 1 without generating all 10 elements. So g = 3 is not a generator of Z*_11. The order of 3 is 5, which divides p - 1 = 10.
Key fact: the order of any element g in Z*_p must divide p - 1. If the order equals p - 1, then g is a generator. If it is a proper divisor, g is not a generator.
How to check efficiently: compute g^1, g^2, ... mod p until you either reach 1 (not a generator if this happens before step p - 1) or exhaust all p - 1 values (generator).
Alice and Bob agree on a prime p = 19 and generator g = 10 of Z*_19. They wish to establish a shared secret key.
Setup:
Alice picks secret exponent a = 5, sends x = g^a mod p = 10^5 mod 19
Bob picks secret exponent b = 8, sends y = g^b mod p = 10^8 mod 19
Computing Alice's public value:
10^2 ≡ 100 ≡ 5 (mod 19), so Alice's exponent is 2 (since 10^2 mod 19 = 5). More carefully: since 10 is a generator of Z*_19, the first equation 10^2 ≡ 100 ≡ 5 (mod 19) implies a = 2, and the third equation 10^8 ≡ 6^2 ≡ 36 ≡ 17 (mod 19) implies b = 8.
Finding the shared secret key:
By the Diffie-Hellman protocol, the shared secret key is g^(ab) mod p.
17^a = 17^2 = 289 ≡ 4 (mod 19), since 289 = 15 · 19 + 4.
Alternatively, since a = 2 is small, it is convenient to note that 17 ≡ -2 (mod 19), so 17^2 = (-2)^2 = 4 (mod 19).
The shared secret key is 4.
Alternative computation using b = 8: compute 5^8 mod 19 using repeated squaring: 5^2 = 25 ≡ 6, 5^4 = 6^2 = 36 ≡ 17, 5^8 = 17^2 = 289 ≡ 4 (mod 19). Same answer.
The protocol's security rests on the discrete logarithm problem: given g^a mod p, it is computationally hard to recover a when p is large.
RSA is a public-key cryptosystem built on the difficulty of factoring large numbers.
Key generation:
Choose two large primes p and q. Compute n = p · q.
Compute φ(n) = (p - 1)(q - 1).
Choose a public exponent e with gcd(e, φ(n)) = 1.
Compute the private exponent d such that e · d ≡ 1 (mod φ(n)).
Public key: (n, e). Private key: d.
Encryption: given plaintext m, compute ciphertext c = m^e mod n.
Decryption: given ciphertext c, recover plaintext m = c^d mod n.
Worked example from the cheat sheet:
Suppose n = 3 · 11 = 33 (so p = 3, q = 11). The public exponent e = 7. The decryption exponent d is the inverse of e modulo φ(n) = (3-1)(11-1) = 20. Since 7 · 3 = 21 ≡ 1 (mod 20), we have d = 3.
To encrypt m = 2: c = 2^7 mod 33. Compute 2^7 = 128 = 3 · 33 + 29, so c = 29.
To decrypt c = 29: m = 29^3 mod 33. Compute 29^2 = 841 = 25 · 33 + 16, so 29^2 ≡ 16 (mod 33). Then 29^3 = 29 · 16 = 464 = 14 · 33 + 2, so m = 2. We recover the original message.
Why it works: by Fermat's Little Theorem (generalised via the Chinese Remainder Theorem), m^(ed) ≡ m (mod n) whenever gcd(m, n) = 1.
A blood test for a rare disorder is being performed on n people. Each person can be tested individually, but this is expensive. To reduce the cost, the n people are divided into n/k groups G_1, G_2, ..., G_{n/k}, of k people each. The blood samples of people in a group are pooled and tested together, so that only n/k tests are used initially. If the test for group G_i is negative, none of the members have the disorder. If the test is positive, at least one person in the group has the disorder, and the entire group must be retested individually.
Each person independently has a probability p of having the disorder.
Part (a): Probability that a specific group G_i needs individual testing
A group needs individual testing when at least one person has the disorder. The probability that all k are free is (1 - p)^k. So the probability that at least one person has the disorder is:
1 - (1 - p)^k
Part (b): Expected number of groups that need individual testing
Let X_i be an indicator for whether group G_i needs individual testing. Then E[X_i] = 1 - (1 - p)^k. Let X = X_1 + X_2 + ... + X_{n/k} be the number of groups that need individual testing.
By linearity of expectation: E[X] = (n/k) · (1 - (1 - p)^k)
Part (c): Expected total number of tests
No matter what, n/k group tests are required. Then for each group that needs individual testing, k additional tests are required. The total number of tests is Y = n/k + kX.
By linearity of expectation:
E[Y] = n/k + k · E[X] = n/k + k · (n/k)(1 - (1 - p)^k) = (n/k)(1 + k - k(1 - p)^k)
Equivalent forms: E[Y] = n/k + n(1 - (1 - p)^k) = n/k + n - n(1 - p)^k
This is a classic application of indicator random variables and linearity of expectation, which avoids the need to reason about dependent events.
Students often apply Fermat's Little Theorem when gcd(a, p) ≠ 1. The theorem requires a to be coprime with p. If p divides a, then a^(p-1) ≡ 0 (mod p), not 1.
When checking if g is a generator of Z*_p, you must verify that g's order is exactly p - 1. It is not enough to show g produces some elements; you need all p - 1 of them.
In Diffie-Hellman, the shared secret is g^(ab) mod p, not g^(a+b) mod p. The exponents multiply, they do not add.
In RSA, the private exponent d is the modular inverse of e mod φ(n), not mod n. Computing d mod n instead of mod φ(n) gives the wrong key.
In group testing probability, students sometimes multiply probabilities for groups rather than using linearity of expectation with indicator variables. Linearity of expectation works regardless of independence, making it the cleaner approach.
⚠️ Fermat's Little Theorem is the backbone of modular exponentiation questions. Know the reduction technique: write N = q(p-1) + r and compute a^r mod p.
⚠️ Generator verification questions require you to compute successive powers and check whether the order is p - 1. Show your work for each power.
⚠️ Diffie-Hellman worked examples are common. You will be asked to find secret exponents, public values, and the shared key. Keep your modular arithmetic clean.
⚠️ RSA questions test key generation (computing φ(n), finding d) and the encryption/decryption cycle. A frequent exam check: encrypt then decrypt and verify you get the original message back.
⚠️ Group testing questions test your ability to set up indicator random variables and apply linearity of expectation. The final expression E[Y] = (n/k)(1 + k - k(1-p)^k) should be derivable from scratch.
True or False: 5^12 ≡ 1 (mod 13). (True, by Fermat's Little Theorem since 13 is prime and gcd(5,13) = 1)
True or False: Every element of Z*_p is a generator. (False, only elements with order p - 1 are generators)
Fill in the blank: In Diffie-Hellman, the shared secret key is g^______ mod p. (ab)
True or False: In RSA, the decryption exponent d satisfies e · d ≡ 1 (mod n). (False, it is mod φ(n))
True or False: Linearity of expectation requires the random variables to be independent. (False, it holds regardless of independence)
Q: Compute 3^2026 mod 11 using Fermat's Little Theorem.
A: Since 11 is prime, 3^10 ≡ 1 (mod 11). Write 2026 = 10 · 202 + 6. So 3^2026 ≡ 3^6 (mod 11). Compute 3^3 = 27 ≡ 5, then 3^6 = 5^2 = 25 ≡ 3 (mod 11). Answer: 3.
Q: Is g = 3 a generator of Z_11? Justify.*
A: No. The powers of 3 mod 11 are: 3, 9, 5, 4, 1. The order is 5, which is less than p - 1 = 10. Since the order does not equal 10, g = 3 is not a generator.
Q: Alice and Bob use Diffie-Hellman with p = 19, g = 10. Alice sends x = 5, Bob sends y = 17. What is the shared secret key?
A: Alice computes y^a = 17^2 = (-2)^2 = 4 (mod 19). The shared secret key is 4.
Q: In the group testing problem, write the expected total number of tests when n people are divided into groups of size k, each person having disorder probability p.
A: E[Y] = n/k + n(1 - (1 - p)^k). This is n/k initial group tests plus the expected number of individual retests.
Q: In RSA with p = 3, q = 11, and e = 7, what is the decryption exponent d?
A: φ(n) = 2 · 10 = 20. We need d such that 7d ≡ 1 (mod 20). Since 7 · 3 = 21 ≡ 1 (mod 20), d = 3.
Fermat's Little Theorem, modular exponentiation, modular arithmetic, Z*_p, multiplicative group, generator, primitive root, order of an element, Diffie-Hellman key exchange, discrete logarithm problem, RSA, public-key cryptography, encryption, decryption, private key, public key, group testing, blood test, indicator random variable, linearity of expectation, expected value, EECS 376, foundations of computer science, University of Michigan