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