📂Number Theory

Discrete Logarithms

Definition ¹

Let’s say that for a prime number $p$, the identity element in the Galois Field $\mathbb{F}_{p} := \mathbb{Z} / p \mathbb{Z}$ is $0$.

Then, for a primitive root $g \ne 0$ of $\mathbb{F}_{p}$, a function $\log_{g} : \mathbb{F}_{p}^{ \ast } \to \mathbb{Z} / (p-1) \mathbb{Z}$ defined on a cyclic group $\mathbb{F}_{p} ^{ \ast } := \mathbb{F}_{p} \setminus \left\{ 0 \right\} = \left< g \right>$ that satisfies the following is called a Discrete Logarithm. $$g^{ \log_{g} (h) } \equiv h \pmod{p}$$

Explanation

The existence of $\mathbb{F}_{p} ^{ \ast }$ is guaranteed by the Primitive Root Theorem.

In fact, the discrete logarithm becomes an isomorphism because it applies to all $a,b \in \mathbb{F}_{p}^{ \ast }$ such that $\log_{g} (ab) = \log_{g} (a) + \log_{g} (b)$.

Unlike ordinary logs, the log in cryptography is useful because of the difficulty of its calculation, for given $k$, $$g^{k} \equiv x \pmod{p}$$ finding $x$ that satisfies it is not too difficult using the method of successive squaring, however, for a given $h$, $$g^{x} \equiv h \pmod{p}$$ finding $x$ that satisfies it is hard. This is called the Discrete Logarithm Problem, and it possesses essential properties of a cipher, making it widely used throughout cryptography.

Moreover, the discrete logarithm problem can also be generalized over group $\left( G , \ast\ \right)$. The issue itself still asks $$g \ast\ \cdots \ast\ g = h$$ how many times one must find $g \ast\ g$ to satisfy it. This implies that the limitation of cryptography is not in number theory.

See Also

• Discrete Logarithm Problem

Cryptographic Algorithms that Utilize the Difficulty of the Discrete Logarithm Problem

• Diffie-Hellman Key Exchange Algorithm
• ElGamal Public Key Cryptosystem

Attack Algorithms on the Discrete Logarithm Problem

• Shanks’ Algorithm
• Pollard’s Rho Algorithm
• Conditions where the Discrete Logarithm Problem is Easily Solvable