An Interactive Applet powered by Sage and MathJax.

(By Alyssa Vorpahl and Prof. Gregory V. Bard)

This page will discuss the discrete logarithm problem, a problem that is very important in modern cryptography. Computing the discrete logarithm is assumed to be hard. Moreover, if an efficient way to solve discrete logarithms were to be found, it would render many current tools in cryptography useless - including the Diffie-Hellman Key Exchange protocol.

The discrete logarithm problem requires two things: That you are working with a group G, and that g is a generator of G. Then, for a given y in G, can you find a positive integer x such that g^{x} = y? By the way, this problem can be done in many different groups G, but we will discuss the integers mod p for simplicity. In cryptography, elliptic curves are often used for the group G, as well as the integers mod p.

Notably, when the group you're working with is Z_{p} for a very large value of p, and you consider multiplication to be the group's operation, finding the required integer x (given some G, a generator g in G, and some y in G) is difficult. That's why the Diffie-Hellman Key Exchange protocol is trusted.

If there were a fast algorithm to determine the unique solution to this problem, it would prove problematic for several tools of today's cryptography. However, there are ways to solve it that are not fast enough to be a problem.

First, we will explore how difficult this problem is to solve by brute force. We will perform a number of modular exponentiations (in worst case) equal to the size of G. Later we will see how, with the Baby-Step/Giant-Step method, this can be reduced to a number of modular exponentiations proportional to the square root of the size of G, which is shockingly smaller for moderately large G. Yet, cryptography uses huge groups G, so even the Baby-Step/Giant-Step method is infeasible.

In this context, brute-force attack means trying every possible x value. Given the group G, the desired y in G, and the generator g in G, we can loop through each x value from 0 to Phi(p) until we find an integer x where g^{x}> = y mod p.

By the way, the discrete logarithm is not unique. Suppose g^{x} = y and phi = Phi(p). Because x^{phi} = 1 mod p for any x coprime to p, we have the following behavior:

- g
^{x+(k*phi)}= g^{x}*g^{k*phi}= g^{x}*(g^{phi})^{k}= g^{x}*1^{k}= g^{x}*1 = g^{x}= y mod p

which means that x, x+phi, x+2*phi, ... are all solutions of the discrete logarithm.

So, discrete logarithms are not unique when the answer is considered an integer. However, discrete logarithms *are* unique when the answer is considered an integer mod phi.

Once you load the applet, there will be 3 sliders: one to control the desired y value, one to control the modulus p for the group Z_{p}, and one to control the generator g. Once all of the initial conditions are verified (the modulus must be a prime, g must generate Z_{p}, and 0 < y < p) to ensure that the discrete logarithm problem has a solution.

Once that has been verified, every possible x value will be looped through until g^{x} = y. That x will be flagged as the solution, and the loop will end.

Last modified by Alyssa Vorpahl on December 8th, 2018. Updated to Python 3 by Prof. Bard on April 10th, 2020.