Number Theory: Discrete Log Problem and Primitive Roots

17 Dec 2021

Notes Cryptography 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

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