# Number Theory: Discrete Log Problem and Primitive Roots

## 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.