Programming Praxis

5 Responses to “Discrete Logarithms”

1. Daniel said

   May 4, 2016 at 1:14 AM

   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

   May 4, 2016 at 2:24 AM

   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.

   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

   May 5, 2016 at 7:03 AM

   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

   May 5, 2016 at 10:12 AM

   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. Pollard’s Rho Algorithm For Discrete Logarithms | Programming Praxis said

   May 27, 2016 at 12:59 PM

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