# 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)
...
```