## You are here

Homediscrete logarithm

## Primary tabs

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

Synonym:

index

Type of Math Object:

Definition

Major Section:

Reference

Groups audience:

## Mathematics Subject Classification

11A15*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections