Question

Problem 7 | Discrete logarithms with respect to different primitive roots

Prove that the difficulty of the discrete logarithm problem is independent of the primitive root.
Specifically, for any prime p, assuming that it is computationally feasible to extract discrete
logarithms with respect to one primitive root of p, show how one can feasibly extract discrete
logarithms with respect to any other primitive root of p.

Answer 1

Let p be a prime.

We say that g is a primitive root of p (or sometimes modulo p), if the powers l1, l2, l3,……, lp−1 are congruent, in some order, to 1, 2, 3, ……, p−1 (modulo p).

when we consider the remainders when lk is divided by p, all numbers between 1and p−1 are remainders (0 cannot).

We know fermat's Theorem

, lp−1≡1(modp)

So lp−1, the power of l start all over again modulo p, therefore lp≡l, lp+1≡l2, .....

we can say l is a primitive root of p if l is also a generator of the multiplicative group on non-zero objects under modulo p. every prime has a primitive root.

Large primes p have many primitive roots.

For eg. Let p=7, and let l=2.

The power of 2, reduced modulo 7, are 2, 4,1, 2, 4, ……. ,

2 is not a primitive root of 7. Now take l=3.

powers of 3, reduced modulo 7, are 3, 2, 6, 4, 5, 1, 3, ……, therefore 3 is a primitive root of 7.

Let l be known primitive root of the prime p,

Assume

a is relatively prime to p.there exists a unique integer k, with 1≤k≤p−1

St

lk≡a(modp)

So no k is known the indexof a with respect to the primitive root l.

Here k is called the discrete logarithm of a (wrt primitive root l).

discrete logarithms have properties similar to ordinary logarithms.

discrete logarithms are exponents, exactly as ordinary logarithms.:

They are good because they are used in cryptography.

l and k, it is computation

l and a, it seems to be computationally very hard to find the k between 1 & p−1 st lk≡a(modp).

Therefore discrete logarithm when a very large prime is involved, seems to be computationally very difficulty