4827.sagews

Discrete Log Problem:

The general problem is this:  Given $a=b^n$, solve for $n$.  This is easy for real numbers ... just use the logarithm.

Example:  Find the number $n$ if $b^n=19683$.  

Solution:  We quickly find that $n=\log _3(19683) = \log(19683) / \log(3) = 9$ (as seen in below computations).

log(19683.0)

log(3.0)

log(19683.0)/log(3.0)

Note:  SAGE uses a rapidly-converging infinite series to compute approximations for $\log(x)$.  In other words, this computation is EASY for a computer to do.  This should be expected, though, by looking at the following graph of $\log(x)$.  Notice how (1) smooth; and (2) predictable it is.

plot(log,0.1,10,figsize=[4,4])

On the other hand, things get more difficult with computing "discrete" logarithms (i.e., logarithms in modular arithmetic).

Here is the formal statement of the "discrete log problem":

Discrete Log Problem:  Let $G$ be a finite field (such as $\mathbb{Z}/p\mathbb{Z}$ for some prime number $p$).  Given $b\in G$ and a power $a$ of $b$, find a positive integer $n$ so that $b^n=a$.

This is a VERY difficult problem in practice.  The reason is that the (minimum) logarithm of a number mod $n$ bounces quite randomly.  This behavior is illustrated in the following plot:

p=23                                            
R=Integers(p)                                   
a=R.multiplicative_generator()                  
v=sorted([(a^n,n) for n in range(p-1)])         
G=plot(point(v,pointsize=50,color="red"))
H=plot(line(v,color="blue"))
show(G+H,figsize=[4,4])

Fortunately (or unfortunately, depending on your perspective), there is an inefficient algorithm for computing a discrete log.  We'll call this the "Brute Force" Algorithm.  Simply, you try $b^1$, $b^2$, $b^3$, etc. until you find the correct exponent so that $b^n=a$.

Consider the following example:  Find $n$ so that $5^n\equiv 37 \pmod{97}$.

The brute force approach would be to calculate $5^1$, $5^2$, $5^3$, $\dots$ until you get 18 (remember to work mod 23).  SAGE can help with this:

Mod(5,97)^1

Mod(5,97)^2

Mod(5,97)^3

Mod(5,97)^4

Note:  it will take a while, but you'll finally find the correct exponent:

Mod(5,97)^91

The downside to this approach is that when $p$ is large, computing the discrete log this way soon becomes quite impractical, because increasing the number of digits of the modulus makes the computation take MUCH longer.

Note:  you can save some time from having to input one computation at a time by simply constructing a FOR loop.  Guess at an upper bound for your unknown power $n$, and iterate the $5^n\pmod{23}$ reduction over n=0, 1, 2, ... up to your upper bound.  Then, print the results of each computation and inspect the list for the correct answer.  If it doesn't show up, increase your upper bound and try again.

The previous example can be seen below.  Notice that for exponent $n=12$, the answer is 18, just as before.

upperBound=20
for n in range(upperBound):
    b=Mod(5,97)^n
    print(n,b)