# 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},\mathrm{\dots},{g}^{p-2}\}$.
For a number $x\in G$ we want to know the unique number $0\le n\le 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 ${\mathrm{ind}}_{g}(x)$. For $x,y\in G$ it satisfies the following properties:

${\mathrm{ind}}_{g}(xy)$ | $={\mathrm{ind}}_{g}(x)+{\mathrm{ind}}_{g}(y);$ | ||

${\mathrm{ind}}_{g}({x}^{-1})$ | $=-{\mathrm{ind}}_{g}(x);$ | ||

${\mathrm{ind}}_{g}({x}^{k})$ | $=k\cdot {\mathrm{ind}}_{g}(x).$ |

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

${\mathrm{ind}}_{h}(x)$ | $={\mathrm{ind}}_{h}(g)\cdot {\mathrm{ind}}_{g}(x);$ | ||

$1$ | $={\mathrm{ind}}_{g}(h)\cdot {\mathrm{ind}}_{h}(g);$ | ||

${\mathrm{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 |