Application: The discrete log problem

Let $p$ be a prime number and let $1<a<p$ be an integer. Let $(\mathbb{Z}/p\mathbb{Z})^\times$ denote all the non-zero elements of $\mathbb{Z}/p\mathbb{Z}=\{\overline{0},\overline{1},...,\overline{p-1}\}$ . Consider the map $e_a:\mathbb{Z}\rightarrow (\mathbb{Z}/p\mathbb{Z})^\times$ ,

$$e_a(n)=a^n ( {\rm mod} p), n\geq 0.$$

When this ``exponential map'' is onto then $a$ a primitive root mod $p$ . If the order of $a ( {\rm mod} p)$ is $p-1$ then $a$ 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 $y>0$ is given and you you want to solve $\exp(x)=y$ for $x$ (i.e., take the log of $y$ ) then you can use a pocket calculator to quickly find a ``good'' approximation for $x$ (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 $\exp(x)$ which converges rapidly and which can be ``hard wired'' into the calculators circuitry.

Discrete log problem: Given a non-zero $b$ in $\mathbb{Z}/p\mathbb{Z}$ , if $e_a(n)=b$ holds for some $n$ then find $n$ . (The smallest such $n>0$ , if it exists, is called the discrete log of $b$ to base $a$ mod $p$ .)

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