# Discrete Logarithm Problem

**Posted:**June 9, 2020

**Filed under:**Kuliah Comments Off on 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*

_{5}

^{*}, and the generator is 2, then the discrete logarithm of 1 is 4 because 2

^{4}≡ 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 2*q*+1 where *q* is a large prime number. This guarantees that *p*-1 = 2*q* 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