Application: The discrete log problem

Let be a prime number and let be an integer. Let denote all the non-zero elements of . Consider the map ,

When this exponential map'' is onto then a primitive root mod . If the order of is then is a primitive root.

Though this map is analogous to the exponential map on the real numbers, there are some big differences between them! For example, if is given and you you want to solve for (i.e., take the log of ) then you can use a pocket calculator to quickly find a good'' approximation for (where by good'' we mean the approximate answer the calculator gives you is probably close enough for the application you have in mind). It is worth emphasizing that the calculator will return an answer almost instantly. This basically comes from the fact that, thanks to calculus, there is a Taylor series expansion for which converges rapidly and which can be hard wired'' into the calculators circuitry.

Discrete log problem: Given a non-zero in , if holds for some then find . (The smallest such , if it exists, is called the discrete log of to base mod .)

The situation of computing logs is different in the discrete setting. Given a non-zero in , even if you know holds for some (we know this is true when is a primitive root mod ), it doesn't make sense to ask for an approximation'' to . More seriously though, there is no fast'' algorithm known to compute given and . Moreover, it should be emphasized that the security of many cryptographic schemes depend on this fact'' that the discrete log problem is hard''.

david joyner 2008-04-20