discrete logarithm
Let be a prime. We know that the group is cyclic. Let be a primitive root of , i.e. . For a number we want to know the unique number with
This number is called the discrete logarithm or index of to the basis and is denoted as . For it satisfies the following properties:
Furthermore, for a pair of distinct primitive roots, we also have, for any :
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 |