PlanetMath: discrete logarithm

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (210)
Orphanage
Unclass'd (1)
Unproven (472)
Corrections (38)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

discrete logarithm

(Definition)

Let be a prime. We know that the group $G:=(\mathbb{Z}/p\mathbb{Z})^*$ is cyclic. Let be a primitive root of , 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

$\displaystyle x=g^n.$

This number

is called the discrete logarithm or index of

to the basis

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

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.

"discrete logarithm" is owned by mathwizard. [ full author list (2) | owner history (2) ]

(view preamble)

Other names:

index

Log in to rate this entry.
(view current ratings)

Cross-references: cryptography, properties, basis, logarithm, primitive root, cyclic, group, prime
There are 32 references to this entry.

This is version 4 of discrete logarithm, born on 2004-12-21, modified 2008-03-08.
Object id is 6592, canonical name is DiscreteLogarithm.
Accessed 4710 times total.

Classification:

AMS MSC:

11A15 (Number theory :: Elementary number theory :: Power residues, reciprocity)

Pending Errata and Addenda

None.[ View all 2 ]

Discussion

forum policy

No messages.

Interact