Motivation§

We introduce the discrete log problem (DLP), the basis of many cryptosystems is founded upon the fact that it is very difficult to solve.

The Discrete Log Problem§

Discrete Log Problem

Given $h, y$ are non-zero elements belonging to $\mathbb{Z}_p$, where $p$ prime, the discrete log problem is finding an exponent $x$ such that

$$ g^x \equiv_p y. $$

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.

Primitive Roots§

Theorem 6.1

Let $p$ be prime, then there exists an element $g \in \mathbb{Z}_p$ with powers giving every element ${1, \dots, p-1} \leftrightarrow {1,g,g^2,\dots,g^{p-2}}$.

Primitive Roots

From Theorem 6.1, the values of $g$ are called “primitive roots”.

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