Next: Modular exponentiation as a Up: An easy problem and Previous: An easy problem and

How modular logarithms differ from ordinary logarithms

The modular logarithm seems to resemble the ordinary, nonmodular logarithm. The ordinary base b logarithm of c is defined to be the real number x such that . This equation reminds one of the (modular) equation defining the modular logarithm. Moreover, like the modular logarithm, an ordinary logarithm question sometimes has no answer (when the input c is nonpositive). You can calculate ordinary logarithms on a scientific calculator, at least base-10 logarithms. Why should the modular logarithm problem be difficult when the ordinary logarithm problem is so easy that a calculator can solve it?

The answer seems to have something to do with approximation. A calculator typically isn't calculating an exact logarithm; it's calculating an approximate logarithm. For example, my calculator tells me that the base-10 logarithm of 17 is 1.2304489 but when I test this answer by raising 10 to the power of 1.2304489, my calculator tells me the answer is not 17 but 16.999999. In fact, the base-10 logarithm of 17 can't be represented exactly using a finite number of digits. Why am I satisfied with a calculator that gives me a wrong answer? The fact that 10 to the power of 1.2304489 is very close to 17 tells me that in fact the base-10 logarithm of 17 is very close to 1.2304489. Thus the answer my calculator gives me is very close to the exact answer. Moreover, since 10 to the power of 1.2304489 is smaller than 17, we can conclude that 1.2304489 is smaller than the exact base-10 logarithm of 17. These kinds of observations were used to formulate a good algorithm for calculating a good approximation to a logarithm.

Contrast this situation with that arising in modular arithmetic. Let the modulus m be 97330327. What is the base-2 logarithm of 88319671? That is, we want to calculate the number k such that

By trying different exponents, I happened across the exponent 28305819, which leads to a different but similar number:

This suggests that 28305819 might be a good approximation to the log of 88319671. Also, since the result of exponentiating to the power of 28305819 is a standard name smaller than 88319671, one might be tempted to guess that 28305819 is smaller than the exact logarithm of 88319671.

In fact, the true logarithm is 12314, which is very different from our guess of 28305819 and is smaller than it. We conclude that, in modular arithmetic in contrast to ordinary arithmetic, just because two numbers are close does not mean their logarithms are close.

I shouldn't need to say this, but it is also true that the value of a number's modular logarithm generally has no resemblance to the value of that number's ordinary logarithm. For example, the ordinary base-2 logarithm of 88319671 is roughly 26.396231. It is only very rarely that the modular logarithm equals the ordinary logarithm. (This happens when the ordinary logarithm is exact and is so small than the base to that logarithm is still smaller than the modulus. For example, the ordinary base-2 logarithm of 16384 is precisely 14; since 16384 is smaller than the modulus 97330327, the modular base-2 logarithm of 16384 is also 14.)

Next: Modular exponentiation as a Up: An easy problem and Previous: An easy problem and

Lisa Eckstein
Thu Nov 21 01:20:27 EST 1996