[yyhgddlx] Computing discrete logarithms in Pari/GP

We demonstrate computing the base-2 discrete logarithm of 3 in the Galois field F13; that is, we solve 2^x = 3 (mod 13).

First, we verify in two different ways that 2 is a generator of the field; i.e., the logarithm will actually have an answer.

? znprimroot(13)
Mod(2, 13)
? znorder(Mod(2,13))
12

We calculate the discrete log:

? znlog(Mod(3,13),Mod(2,13))
4

One can verify that 2^4 = 16 = 3 (mod 13).

The first argument doesn't have to be a Mod:

? znlog(3,Mod(2,13))
4

It also works if the modulus of the first argument is a multiple of the modulus of the second (order of the field).  I don't know why this works.

? znlog(Mod(3,13000),Mod(2,13))
4

For much larger fields, primes much larger than 13, computing discrete logarithms is (believed) very difficult, underpinning the cryptographic security of Diffie-Hellman.

However, if P-1 factors into small primes, then the discrete logarithm can be computed very quickly, as demonstrated below with the 3704-bit primorial prime 2657#+1.  Pari/GP presumably implements the Pohlig-Hellman algorithm.

? #
timer = 1 (on)
? p=1+prod(i=1,384,prime(i));
? ispseudoprime(p)
time = 116 ms.
1
? log(p)/log(2)
3703.5958914248503247849893412029101200
? g=znprimroot(p);
time = 6,885 ms.
? lift(g)
time = 4 ms.
2
? x=znlog(3,g);
time = 28,928 ms.
? log(x)/log(2)
3702.5604196061814772849357407769680133
? lift(Mod(2,p)^x)
time = 52 ms.
3

znlog can take additional arguments, the order of the multiplicative group and its factorization, which might accelerate computations, but we do not explore this feature here.