The discrete logarithm problem

Given a group, we can apply the operation repeatedly on a point \( g \) to get to a point \( P \), that is \( g^k=g\times g\times g\times ... \times g=P \). For example, in \( (\mathbb{Z}/7\mathbb{Z})^\star \), \( 5 \) generates all the elements by successive multiplications with itself. We could then ask how many times \( x \) should we multiply \( 5 \) with itself to get to \( 3 \), that is, \( 5^x\equiv 3 \pmod{7} \). Since we know that the order of the group is \( 6 \), we should only concern ourselves with numbers \( 0-6 \). If we look above or try all combinations, \( 5^5\equiv 3 \pmod{7} \) so \( x=5 \). Similarly, if we look for \( y \) such that \( 5^y\equiv 4 \pmod{7} \), we get \( y=2 \). The problem of finding \( x \) so that \( g^k=P \) is known as the discrete logarithm problem (in number theory, \( x \) and \( y \) are known as indices). We quickly see that this logarithm works quite differently from the common logarithm on the real numbers (though the idea is the same, given \( y \), find \( x \) such that \( e^x=y \)). There is no obvious pattern, it is not increasing and if we had to search over a large set, it could be really daunting. Many cryptographic systems rely on the hardness of this problem over a finite cyclic group.