Computing discrete logs over GF(2 ^ n) in practice

Quick how-to

# sage
K.<x> = GF(2 ** n, impl='pari_ffelt') # invoke pari via SageMath's bindings
g = K(x ** 4 + x ** 2 + 1)
h = g ** 123
h.log(g) 	
# => 123

The exact implementation SageMath uses for .log() with pari_ffelt can be found here.

Even for a (relatively) large $n$ this seems to be instantaneous, as opposed to the default implementation which simply hangs.

Other things to note

Performing this calculation directly (in PARI/GP), e.g.

# gp
x = ffgen(2^n, 'x)
g = x^4 + x^2 + 1 
h = g^123
fflog(h, g)
# => 123

makes PARI earnestly hand you a misleading result. As it turns out, ffgen(2^n, 'x) generates an irreducible monic polynomial of degree $n$ over $\mathbb{F}_{p}$ which serves as the modulus of your $\mathbb{F}_{p^n}$.

There’s no finite field structure in PARI. Finite fields are represented only with their elements (FFELTs).

# gp
x.mod
# => degree n irreducible monic
g.mod
# => same degree n irreducible monic

To avoid this, you can supply your own modulus. Irreducibility is not checked.

# gp
x = ffgen(modulus)
...