Discrete Logarithms

May 3, 2016

We use expm from the Standard Prelude:

(define (discrete-logarithm x n m)
  (do ((y 0 (+ y 1)))
      ((= (expm x y m) n) y)))

Here is a sample calculation, with a demonstration that it is correct:

> (discrete-logarithm 3 13 17)
4
> (expm 3 4 17)
13

You can run the program at http://ideone.com/ipFUTa.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: