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