discrete logarithm

Let $p$ be a prime. We know that the group $G:=(\mathbb{Z}/p\mathbb{Z})^{*}$ is cyclic. Let $g$ be a primitive root of $G$ , i.e. $G=\{1,g,g^{2},\dots,g^{p-2}\}$ . For a number $x\in G$ we want to know the unique number $0\leq n\leq p-2$ with

x=g^{n}.

This number $n$ is called the discrete logarithm or index of $x$ to the basis $g$ and is denoted as $\operatorname{ind}_{g}(x)$ . For $x,y\in G$ it satisfies the following properties:

	$\displaystyle\operatorname{ind}_{g}(xy)$	$\displaystyle=\operatorname{ind}_{g}(x)+\operatorname{ind}_{g}(y);$
	$\displaystyle\operatorname{ind}_{g}(x^{-1})$	$\displaystyle=-\operatorname{ind}_{g}(x);$
	$\displaystyle\operatorname{ind}_{g}(x^{k})$	$\displaystyle=k\cdot\operatorname{ind}_{g}(x).$

Furthermore, for a pair $g, h$ of distinct primitive roots, we also have, for any $x\in G$ :

	$\displaystyle\operatorname{ind}_{h}(x)$	$\displaystyle=\operatorname{ind}_{h}(g)\cdot\operatorname{ind}_{g}(x);$
	$\displaystyle 1$	$\displaystyle=\operatorname{ind}_{g}(h)\cdot\operatorname{ind}_{h}(g);$
	$\displaystyle\operatorname{ind}_{g}(-1)$	$\displaystyle=\frac{p-1}{2}.$

It is a difficult problem to compute the discrete logarithm, while powering is very easy. Therefore this is of some interest to cryptography.

Title	discrete logarithm
Canonical name	DiscreteLogarithm
Date of creation	2013-03-22 14:54:27
Last modified on	2013-03-22 14:54:27
Owner	mathwizard (128)
Last modified by	mathwizard (128)
Numerical id	7
Author	mathwizard (128)
Entry type	Definition
Classification	msc 11A15
Synonym	index