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