The ordinary logarithm problem: given a base
b and a number
x, find
y such that
b^
y =
x. So, e.g., the logarithm to base 2 of 128 is 7. This is usually done by calculating the logarithm of
x to base 10, and dividing that by the logarithm of
b to base 10.
We can do this in modular arithmetic too. Suppose we know, for a particular choice of
n,
x,
b, that there is a
y such that
b^
y =
x (mod
n); then finding that
y is the
DiscreteLogarithmProblem modulo
n.
This won't be possible for all
n,
x,
b, but (for instance) if
n is a
PrimeNumber, there is always a
b that makes the problem solvable for every
x other than 0.
The problem generalizes further. The integers modulo a
PrimeNumber p form a
FiniteField; there are other finite fields (exactly one of size
p^
k for each prime
p and positive integer
k), and we can pose the same sort of problem in any of them. The fields of size 2^
k are particularly nice to work with using computers.
The
DiscreteLogarithmProblem is useful in cryptography, for the following reason: suppose
n is large; then given
n,
b,
y it's easy to find
x, but no algorithm is known that, given
n,
b,
x, will efficiently find
y. So the function that takes
y to
x seems to be a "one-way function", much like the one that takes two prime numbers and yields their product. One-way functions are an essential building block for public-key cryptography. The difficulty of solving the discrete logarithm problem is essential for the security of the
DiffieHellmanMerkle key exchange protocol and the
ElGamal cryptosystem.
CategoryMath CategoryCryptography