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

5 Responses to “Discrete Logarithms”

  1. Daniel said

    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
    }
    
  2. Daniel said

    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
    }
    
  3. matthew said

    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]

  4. matthew said

    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)

  5. […] studied discrete logarithms in two previous exercises. Today we look at a third algorithm for computing discrete algorithms, invented by John […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: