Discrete Log Problem and Primitive Roots

§ Overview

In complexity theory, we often reduce one problem into another and say that it is at least as hard. The discrete log problem (DLP) is often "the other problem"; it is difficult to solve as it belongs in the class $\textbf{co-NP} \cap \textbf{NP}$, meaning that if a problem is able to be reduced to DLP it at least belongs into this class.

§ The Discrete Log Problem

There may not exist an exponent $x$ for all $g$ and $y$, the simplest counterexample would be $g = 1$, then the discrete log problem only has a solution if $y = 1$ as well.

The discrete log problem is in $\textbf{NP}\cap\textbf{coNP}$. We do not know of an efficient method to solve the discrete log problem, and we will investigate some methods that work in specific instances of the discrete log.

§ Complexity

As stated earlier, it is believed that the discrete log problem belongs to $\textbf{co-NP} \cap \textbf{NP}$ and no polynomial time algorithm exists to solve it.

In this chapter we will explore various ways that the DLP can be solved if the group has some specific properties.

But the naïve method would to brute-force the problem via trial multiplication, i.e. given a DLP $g^x \equiv_p y$ we would try to solve $\log_g y$ by raising $g$ by higher and higher powers until we get $y.$

This method is exponential in the number of digits of the size of the group.

§ Primitive Roots

Primitive roots exist in $\mathbb{Z}_n$ for $n = 1,2,4, p^k, 2p^k$ where $p$ is an odd prime.

§ Contents

In certain cases, properties of the group $\mathbb{F}_p$ allow certain shortcuts to be taken. These shortcuts are still exponential in the number of digits of the size of the group, but the associated constants are smaller.