Discrete Logarithms

May 3, 2016

The discrete logarithm problem is to compute the exponent y in the expression xyn (mod m), given x, n, and m; x and m must be relatively prime, which is usually enforced by taking the modulus m as prime. For instance, in the expression 3y ≡ 13 (mod 17), the discrete logarithm y = 4, since 34 ≡ 13 (mod 17). The discrete logarithm problem is of fundamental importance in some branches of cryptography, and bears many similarities to factoring integers. Although we have states the discrete logarithm problem using integers, in many cases some other group is used, for instance calculating discrete logarithms on an elliptic curve.

The simplest algorithm for finding the discrete logarithm is simply to try each y from 0 to m; if m is prime, one of the y is certain to work. Unfortunately, this algorithm is very slow, taking time O(m). We’ll see better algorithms in future exercises; our purpose today is to introduce the concept of the discrete logarithm, and to provide a known good algorithm as a base for testing future algorithms.

Your task is to write a program that computes discrete logarithms by trying each possible value in succession until the answer is found. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


Pages: 1 2