Question

7. (16 pts) a. Show that 11 is a primitive root of 13. b. What is the discrete logarithm of 4 base 11 (with prime modulus 13)?

Answer 1

a)

To prove:

11 is a primitive root of 13

Let P=13

P-1=12=2.2.3 =2².3

Now we need to check every prime factor

so for all prime factors P-1,

Hence 11 is a primitive root of 13

b)

x=exponent

11=base

13=modulus

4=remainder

it can be re written as

4=11^x(mod 13)

we need to find x for which it is true

for (13)prime modulus ,discrete group x =(1,....13-1)=(1,...12)

when x=1 remainder= 11

when x=2 remainder =9

when x=3 remainder =7

when x=4 remainder =5

when x=5 remainder =3

when x=6 remainder =1

when x=7 remainder =12

when x=8 remainder =10

when x=9 remainder =8

when x=10 remainder =6

when x=11 remainder =4

when x=12 remainder =2

so we get x=11 for which reaminder is 4

and the same remainder will repeat for next 12 values,hence the cycle is formed

it is called generator.

Please give thumbs up.