As we mentioned at the end of the last handout, cryptography exploits the dichotomy between easy computational problems and hard computational problems. We saw in that handout that the following computational problem is easy: even for input numbers with hundreds of digits, a computer can calculate the output in a reasonable amount of time.
modular exponentiation problem
input: modulus m, standard name b, positive integer k
output: standard name c such that
We next give an example of a computational problem that is believed to be hard.
modular logarithm problem
input: modulus m, standard name b, standard name c
output: nonnegative integer k such that 
if
such an integer exists; otherwise, the answer ``none exists''.
If there exists an integer k such that , we
say that k is a mod-m-logarithm (base b) of c. In this class,
we sometimes write this mathematically as
This notation is deceptive in that it suggests that 
is
a function. In fact, as our description of the computational problem
indicates, there is sometimes no modular logarithm for a given
m,b, and c. Moreover, Euler's Theorem
(described in Handout 7) can be used to show that if there is a
modular logarithm, there are an infinite number. Suppose k is the
mod m logarithm base b of c. This means that
By Euler's Theorem, as long as b is relatively to prime to m,
Multiplying these two equations, we get
Finally, using the first law of exponentiation, we get
That is, 
is also a mod m logarithm base b of c.
Thus fails to be a function in two ways: for some
inputs, it has no answers and for some inputs it has many answers.
Nevertheless it is often useful to view it as a function.
We can get away with this behavior because in many cases where it
arises, (1) we know from the start that there is some answer, and (2)
it doesn't matter which answer we get.