Discrete Logarithms
May 3, 2016
The discrete logarithm problem is to compute the exponent y in the expression xy ≡ n (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.
Programming Praxis 
Here’s a Java solution.
static int pow(int a, int b) { if (b == 0) { return 1; } else if (b % 2 == 0) { int aToHalfB = pow(a, b/2); return aToHalfB * aToHalfB; } else { return a * pow(a, b-1); } } static int discreteLog(int x, int n, int m) { for (int y = 0; y <= m; y++) { if (pow(x, y) % m == n) { return y; } } return -1; // error }I realized upon looking at the solution that I should use a better method of modular exponentiation.
I started working on the following problem, but in doing so realized that a modular exponentiation method is already built-in to Java.
https://programmingpraxis.com/2014/08/08/big-modular-exponentiation/
I suppose that implementing modular exponentiation would be a good exercise nonetheless. Anyhow, here’s a Java solution for this problem that uses Java’s built-in modular exponentiation.
static BigInteger discreteLog(BigInteger x, BigInteger n, BigInteger m) { for (BigInteger y = BigInteger.ZERO; y.compareTo(m) <= 0; y = y.add(BigInteger.ONE)) { if (x.modPow(y, m).equals(n)) { return y; } } return BigInteger.valueOf(-1); // error }Since we are checking x^y for y = 1,2.., we are better just multiplying by x (and taking the modulus) each time around the loop. Note also that even if m is prime, we are only guaranteed a result if x is a primitive root modulo m (there are phi(m-1) primitive roots for prime m).
import sys def plog(x,n,m): x,n = x%m,n%m t = 1; k = 0 while True: if t == n: return k t,k = t*x%m,k+1 if t == 1: return -1 if k == m: return -1 def test(m): for x in range(1,m): print "%d: %s"%(x,[plog(x,n,m) for n in range(1,m+2)]) test(int(sys.argv[1]))2: [0, 1, 8, 2, 4, 9, 7, 3, 6, 5, -1, 0]
3: [0, -1, 1, 4, 3, -1, -1, -1, 2, -1, -1, 0]
4: [0, -1, 4, 1, 2, -1, -1, -1, 3, -1, -1, 0]
5: [0, -1, 2, 3, 1, -1, -1, -1, 4, -1, -1, 0]
6: [0, 9, 2, 8, 6, 1, 3, 7, 4, 5, -1, 0]
7: [0, 3, 4, 6, 2, 7, 1, 9, 8, 5, -1, 0]
8: [0, 7, 6, 4, 8, 3, 9, 1, 2, 5, -1, 0]
9: [0, -1, 3, 2, 4, -1, -1, -1, 1, -1, -1, 0]
10: [0, -1, -1, -1, -1, -1, -1, -1, -1, 1, -1, 0]
Something got screwed with the formatting there: that is the output for
test(11), 2, 6, 7 and 8 are primitive roots (and phi(10) = 4)[…] studied discrete logarithms in two previous exercises. Today we look at a third algorithm for computing discrete algorithms, invented by John […]