Primitive Roots (Prime Powers), Index Calculus

Lecture 8 Primitive Roots (Prime Powers), Index Calculus Recap - if prime p, then there’s a primitive root g mod p and it’s order mod p is p − 1 = q1e1 q2e2 . . . qrer . We showed that there are integers gi mod p with order ei Q exactly qieiQ (counting number of solutions to xqi − 1 ≡ 0 mod p). Set g = gi ei has order qi = p − 1. Number of primitive roots - suppose that m is an integer such that there is a primitive root g mod m. How many primitive roots mod m are there? We want the order to be exactly φ(m). If we look at the integers 1, g, g 2 , . . . g φ(m)−1 , these are all coprime to m and distinct mod m. If we had g i ≡ g j mod m (0 ≤ i < j ≤ φ(m) − 1), then we’d have g j−1 ≡ 1 mod m with 0 ≤ j − i < φ(m), contradicting the fact that g is a primitive root. Since there are φ(m) of these integers, they must be all the reduced residue classes mod m (in particular if m = p, a prime, then {1, 2, . . . p −1} is a relabeling of {1, g, . . . g p−2 } mod p). Suppose that a is a primitive root mod m, then a ≡ g k mod m. Recall that order of g k is ord(g) φ(m) = (k, ord(g)) (k, φ(m)) So only way for the order to be exactly φ(m) is for k to be coprime to φ(m). Ie., the number of primitive roots mod m is exactly φ(φ(m)) - if there’s at least one. In particular, if m = a prime, then number of primitive roots is φ(p − 1). Conjecture 37 (Artin’s Conjecture). Let a be a natural number, which is not a square. Then there are infinitely many primes p for which a is a primite root mod p. This is an open question. Hooley proved this conditional on GRH, and HeathBrown showed that if a is a prime, then there are at most 2 values of a which fail the conjecture (Definition) Discrete Log: Say p is a prime, and g is a primitive root mod p (ie., 1, g, g 2 . . . g p−2 are all the nonzero residue classes mod p). Say we have a 6≡ 0 mod p. We know a ≡ g k for some k (0 ≤ k ≤ p − 2) - k is called the index or the discrete log of a to the base g mod p. This is a computationally hard problem, and is also used in cryptography. Index Calculus - Let’s say we’re trying to solve a congruence xd ≡ 1 mod p. Any x which satisfied this congruence is coprime to p. So if g is a primitive root 1 mod p, we can write x ≡ g k mod p. New variable is now k: xu ≡ 1 mod p ←→ g kd ≡ 1 mod p ←→ p − 1 = ord(g) divides kd p−1 d ←→ divides k (d, p − 1) (d, p − 1) (p − 1) divides k ←→ (d, p − 1) (p−1) So set of solutions for k is exactly the set of multiples of (d,p −1) (remember k is only modulo p − 1). So we can get all the solutions x by raising g to the exponent p−1 . The number of solutions is k, where 0 ≤ k < p − 1 is a multiple of (d,p−1) (p − 1) p−1 (d,p−1) = (d, p − 1) Similarly, if we’re trying to solve the congruence xd ≡ a mod p (a 6≡ 0 mod p), we can write a ≡ g l mod p so if x ≡ g k as before then g kd ≡ g l mod p. This means that g kd−l ≡ 1 mod p ↔ p − 1|kd − l ↔ kd ≡ l mod p − 1 (k is variable), which has a solution iff (d, p − 1) divides l, in which case it has exactly (d, p − 1) solutions. Note: (d, p − 1) divides l ←→ p − 1 divides l(p − 1) (d, p − 1) p−1 ←→ g l (d,p−1) ≡ 1 ←→ a p−1 (d,p−1) ≡1 mod p mod p Theorem 38. There’s a primitive root mod m iff m = 1, 2, 4, pe , or 2pe (where p is an odd prime). Let’s assume that p is an odd prime, and e ≥ 2. Want to show that there’s a primitive root mod pe . Part 1 - There’s a primitive root mod p2 Proof. Choose g to be a primitive root mod p, and use Hensel’s Lemma to show there’s a primitive root mod p2 of the form g+tp for some 0 ≤ t ≤ p−1. We know (g + tp, p) = 1 since p - g and p|tp. ordp2 (g + tp) must divide φ(p2 ) = p(p − 1). On the other hand, if (g + tp)k ≡ 1 mod p2 then (g + tp)k ≡ 1 mod p ⇔ g k ≡ 1 mod p ⇔ p − 1|k. So p − 1 divides ordp (g + tp). Since ordp (g + tp) is a multiple of p − 1 and divides p(p − 1), it’s either equal to p − 1 or equal to p(p − 1) = φ(p2 ). We’ll show that there’s exactly one value of t for which the former happens. 2 Since there are p possible values of t(0 ≤ t ≤ p − 1), any of these remaining ones give a g + tp which is a primitive root mod p2 . Consider f (x) = xp−1 − 1: mod p it has the root g. Since f 0 (x) = (p − 1)xp−2 and f 0 (g) = (p − 1)g p−2 6≡ 0 mod p, by Hensel’s Lemma there is a unique lift g + tp of g mod p2 satisfying xp−1 ≡ 1 mod p2 . This is the unique lift for which order is p − 1 mod p2 . This proves that there’s a primitive root mod p2 .  Part 2 - Let g be a primitive root mod p2 . Then g is a primitive root mod pe for every e ≥ 2. Proof. Since ordpe (g) divides ϕ(pe ) = pe−1 (p − 1) and also that p − 1| ordpe (g) (as in proof of previous part), ordpe (g) must be pk (p − 1) for some 0 ≤ k ≤ e − 1. We e−2 want to show that k = e − 1. To see that, it’s enough to show that g p (p−1) 6≡ 1 mod pe . We’ll show it by induction (base case is e = 2). g p−1 6≡ 1 mod p2 is true because g is a primitive root mod p2 , so order = p(p − 1). So say we know it for e. e−1 We know that φ(pe−1 ) = pe−2 (p − 1). So g φ(p ) ≡ 1 mod pe−1 assuming that e−1 e−1 g φ(p ) 6≡ 1 mod pe . In other words g φ(p ) = 1 + bpe−1 with p - b. Need to e show it for e + 1 - ie., g φ(p ) 6≡ 1 mod pe+1 . We know that g p gp e−1 e−2 (p−1) (p−1) = 1 + bpe−1 . Raising to power p we get = (1 + bpe−1 )p e−1 = 1 + pbp ≡ 1 + bpe     p p e−1 2 (bpe−1 )3 + . . . + (bp ) + 2 3 mod pe+1 (because for e ≥ 2, 3e − 3 ≥ e + 1 and p| 2e − 1 ≥ e + 1). p 2
so p 2
2 2e−2 b p divisible by p2e−1 and e−1 So g p (p−1) ≡ 1 + bpe mod pe+1 with p - b, which 6≡ 1 mod pe+1 . Completes the induction.  Main Proof. Check 1, 2, 4 directly. p odd, m = pe proved. m = 2pe (p odd) φ(m) = φ(2)φ(pe ) = φ(pe ). Let g be a primitive root mod pe . If g is odd, it is a primitive root mod m. If not odd, then add pe to it. Now show that nothing else works: otherwise, if n = mm0 with m and m0 coprime and m, m0 > 2, we’ll show there does not exist a primitive root mod m. By hypothesis (m, m0 > 2) we know φ(m) and φ(m0 ) are even. So for (a, n) = 1, 3 0 we have (a, m) = 1 = (a, m0 ). So aφ(m) ≡ 1 mod m and aφ(m ) ≡ 1 mod m0 . So 0 0 0 mod m0 aφ(m)φ(m )/2 ≡ (aφ(m) )φ(m )/2 ≡ 1 mod m aφ(m)φ(m )/2 ≡ 1 0 Similarly so, aφ(m)φ(m )/2 ≡ 1 mod n but φ(n) = φ(m)φ(m0 ) so ordn (a) < φ(n). So a can’t be a primitive root mod n. Only remaining candidate is n = 2k for k ≥ 3. No primitive root mod 8 since odd2 ≡ 1 mod 8 (and φ(8) = 4). So if a is odd, a2 = 1 + 8k. Show by induction k−2 that a2 ≡ 1 mod 2k (k ≥ 3). Since φ(2k ) = 2k−1 , we see there does not exist a primitive root mod 2k .  4