Primitive-Roots.pptx

Cryptography

1. Crypto Basics (Primitive Roots) Sk Md Mizanur Rahman, Ph.D. Professor, Cybersecurity Centennial College, Toronto, Canada

2. To test that a is a primitive root of p you need to do the following. First , let s=ϕ(p) where ϕ() is the Euler's totient function. If p is prime, then s=p−1. Then you need to determine all the prime factors of s: p 1 ,…,p k . Finally , calculate a s/pi mod p for all i =1…k , and if you find 1 among residuals then it is NOT a primitive root, otherwise it is . So, basically you need to calculate and check k numbers where k is the number of different prime factors in ϕ(p). How you test

3. Let us find the lowest primitive root of 761: s=ϕ(761)=760=2 3 ×5×19 the powers to test are : 760/2=380, 760/5=152 and 760/19=40 ( just 3 instead of testing all of them) Test 2: 2 380 ≡ 1 mod 761 oops test 3: 3 380 ≡ −1 mod 761 OK 3 152 ≡1 mod 761 oops test 5 (skip 4 because it is 2 2 ): 5 380 ≡1 mod 761 oops test 6: 6 380 ≡ −1 mod 761 OK 6 152 ≡ 67 mod 761 OK 6 40 ≡ −263 mod 761 hooray! So, the least primitive root of 761 is 6 . Example

4. Once you have found one primitive root, you can easily find all the others. Indeed , if  a  is a primitive root mod  p , and  p   is prime (for simplicity), then   a  can generate all other remainders  1…(p−1 ) as powers:  a 1 ≡ a,a 2 ,…, a p − 1 ≡ 1 . And   a m mod p  is another primitive root if and only if   m and  p− 1  are coprime (if  gcd ( m,p−1 )=1). By the way, this is exactly why you have  ϕ(p− 1)  primitive roots when  p  is prime. How you find all the other primitive roots

5. Prime number = 17 3 1 mod 17 3 2 mod 17 3 3 mod 17 3 4 mod 17 3 5 mod 17 3 6 mod 17 3 7 mod 17 3 8 mod 17 3 9 mod 17 3 10 mod 17 3 11 mod 17 3 12 mod 17 3 13 mod 17 3 14 mod 17 3 15 mod 17 3 16 mod 17 3 9 10 13 5 15 11 16 14 8 7 4 12 2 6 1 How you find all the other primitive roots(cont…) Considering “3” as a candidate: Example:

6. GCD(16,2) = 2; GCD(16,3) = 1; so 3 3 mod 17 = 10 is a primitive root of mod 17 GCD(16,4) = 4; GCD(16,5) = 1; so 3 5 mod 17 = 5 is a primitive root of mod 17 GCD(16,6) = 2; GCD(16,7) = 1; so 3 7 mod 17 = 11 is a primitive root of mod 17 GCD(16,8) = 8; GCD(16,9) = 1; so 3 9 mod 17 = 14 is a primitive root of mod 17 GCD(16,10) = 2; GCD(16,11) = 1; so 3 11 mod 17 = 7 is a primitive root of mod 17 GCD(16,12) = 4; GCD(16,13) = 1; so 3 13 mod 17 = 12 is a primitive root of mod 17 GCD(16,14) = 2; GCD(16,15) = 1; so 3 15 mod 17 = 6 is a primitive root of mod 17 How you find all the other primitive roots (cont…)

7. 10 1 mod 17 10 2 mod 17 10 3 mod 17 10 4 mod 17 10 5 mod 17 10 6 mod 17 10 7 mod 17 10 8 mod 17 10 9 mod 17 10 10 mod 17 10 11 mod 17 10 12 mod 17 10 13 mod 17 10 14 mod 17 10 15 mod 17 10 16 mod 17 10 1 How you find all the other primitive roots (cont…) Considering “10” as a candidate: