# 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 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 DiscreteLogarithm 2013-03-22 14:54:27 2013-03-22 14:54:27 mathwizard (128) mathwizard (128) 7 mathwizard (128) Definition msc 11A15 index