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.
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 […]