Discrete Logarithm Problem

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