Discrete Logarithm Problem

Discrete logarithms are logarithms defined with regard to multiplicative cyclic groups. If G is a multiplicative cyclic group and g is a generator of G, then from the definition of cyclic groups, we know every element h in G can be written as g^x for some x. The discrete logarithm to the base g of h in the group G is defined to be x . For example, if the group is Z₅^*, and the generator is 2, then the discrete logarithm of 1 is 4 because 2⁴ ≡ 1 mod 5.

The discrete logarithm problem is defined as: given a group G, a generator g of the group and an element h of G, to find the discrete logarithm to the base g of h in the group G. Discrete logarithm problem is not always hard. The hardness of finding discrete logarithms depends on the groups. For example, a popular choice of groups for discrete logarithm based crypto-systems is Z_p^* where p is a prime number. However, if p−1 is a product of small primes, then the Pohlig–Hellman algorithm can solve the discrete logarithm problem in this group very efficiently. That’s why we always want p to be a safe prime when using Z_p^* as the basis of discrete logarithm based crypto-systems. A safe prime is a prime number which equals 2q+1 where q is a large prime number. This guarantees that p-1 = 2q has a large prime factor so that the Pohlig–Hellman algorithm cannot solve the discrete logarithm problem easily. Even p is a safe prime, there is a sub-exponential algorithm which is called the index calculus. That means p must be very large (usually at least 1024-bit) to make the crypto-systems safe.

Source: https://www.doc.ic.ac.uk/~mrh/330tutor/ch06s02.html

Cyclic Groups and Generators

Some groups have an interesting property: all the elements in the group can be obtained by repeatedly applying the group operation to a particular group element. If a group has such a property, it is called a cyclic group and the particular group element is called a generator. A trivial example is the group Z_n, the additive group of integers modulo n. In Z_n, 1 is always a generator:

1 ≡ 1 mod n

1+1 ≡ 2 mod n

1+1+1 ≡ 3 mod n

…

1+1+1+…+1 ≡ n ≡ 0 mod n

If a group is cyclic, then there may exist multiple generators. For example, we know Z₅ is a cyclic group. The element 1 is a generator for sure. And if we take a look at 2, we can find:

2 ≡ 2 mod 5

2+2 ≡ 4 mod 5

2+2+2 ≡ 6 ≡ 1 mod 5

2+2+2+2 ≡ 8 ≡ 3 mod 5

2+2+2+2+2 ≡ 10 ≡ 0 mod 5

So all the group elements {0,1,2,3,4} in Z₅ can also be generated by 2. That is to say, 2 is also a generator for the group Z₅.

Not every element in a group is a generator. For example, the identity element in a group will never be a generator. No matter how many times you apply the group operator to the identity element, the only element you can yield is the identity element itself. For example, in Z_n, 0 is the identity element and 0+0+…+0 ≡ 0 mod n in all cases.

Not every group is cyclic. For example, Z_n^*, the multiplicative group modulo n, is cyclic if and only if n is 1 or 2 or 4 or p^k or 2*p^k for an odd prime number p and k ≥ 1. So Z₅^* must be a cyclic group because 5 is a prime number. Actually all the elements in Z₅^*, {1,2,3,4} can be generated by 2:

2¹ ≡ 2 mod 5

2² ≡ 4 mod 5

2³ ≡ 8 ≡ 3 mod 5

2⁴ ≡ 16 ≡ 1 mod 5

And Z₁₂^* is not a cyclic group. The elements in Z₁₂^* are: {1,5,7,11}. Obviously the identity element 1 cannot be a generator. Let’s check the other three elements:

None of the elements can generate the whole group. Therefore, none of them is a generator. So Z₁₂^* is indeed not cyclic.

If Z_n^* is cyclic and g is a generator of Z_n^*, then g is also called a primitive root modulo n.

Source: https://www.doc.ic.ac.uk/~mrh/330tutor/ch06.html