CYG Chapter 7 The Discrete Logarithm

Basis of numerous cryptographic protocols // Most famous is ElGamal cs

1. Let n in N\{1} and a in Z_n*

2. ord_n(a)=min{k in {1,…,phi(n)}| a^k equiv 1 (mod n)}

3. If ord_n(a)=phi(n) then a is called “pem n”

1. There exists no 1<=i<j<=phi(n) with aⁱ equiv a^j (mod n) and thus a^j-i equiv 1 (mod n)

2. Hence <a> is a cyclic group

1. <a>={a,a²,…,a^phi(n)}=Z_n* // Consists just of powers of a

2. a is called generator

Is for given n the group Z_n* cyclic or not?

1. Let n in N

2. pem n exists iff n in {2,4,p^k,2p^k|p>=3 prime and k in N}

3. If pem n exists then there exist phi(phi(n)) many

1. Let n=7, phi(n)=6

2. Test a=2 … a³=1 → Not a pem 7

3. Test a=3 … a⁶=1 → Is a pem 7

4. Test a=5 … a⁶=1 → Is a pem 7

5. Because phi(phi(7))=phi(6)=|{1,5}|=2 we know we found all

1. Let a be pem n and y in Z_n*

2. There exists the unique dl x in {0,…,phi(n)-1} with a^x equiv y (mod n) // x=log_ay