discrete logarithm


Let p be a prime. We know that the group G:=(/p)* is cyclic. Let g be a primitive rootMathworldPlanetmath of G, i.e. G={1,g,g2,,gp-2}. For a number xG we want to know the unique number 0np-2 with

x=gn.

This number n is called the discrete logarithmMathworldPlanetmath or index of x to the basis g and is denoted as indg(x). For x,yG it satisfies the following properties:

indg(xy) =indg(x)+indg(y);
indg(x-1) =-indg(x);
indg(xk) =kindg(x).

Furthermore, for a pair g,h of distinct primitive roots, we also have, for any xG:

indh(x) =indh(g)indg(x);
1 =indg(h)indh(g);
indg(-1) =p-12.

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