Discrete Logarithm Problem in $GF(p^m)$

Question

I have question regarding DLP in $GF(p^m)$

I know the algorithms for solving the DLP in $GF(p)$ like Baby Step-Giant Step, Pohlig-Hellman etc...

But what if we move into the $GF(p^m)$ and are working with polynomials? How these algorithms can be modified?

For example, the first step in Pohlig-Hellman algorithm in $GF(p)$ is to factorize order of the group and then calculate DLP modulo each group order divisors, but if we want to use polynomials, how will we start? How should be polynomials treated, when solving DLP?

Appreciate any ideas.

Answer 1

I'm not an expert on this, but list my thoughts anyway. The elements of the field $GF(p^m)$ are, indeed, usually stored as polynomials, but you treat them the same way as you would any elements of a cyclic group where you want to solve a DLP. Residue classes modulo a prime, elements of $GF(p^m)$, points on an elliptic curve. Not much difference,

1. The order of the multiplicative group of $GF(p^m)$ is $p^m-1$. So you can try and factor that for the purposes of applying the Chinese remainder theorem. There will be factors of the form $p^d-1$ for all divisors $d\mid m$, as then $p^d-1\mid p^m-1$. So unless $m$ is a prime number, there are some sizable factors. For this reason $p=2$, $m$ prime, is a popular choice, as then the attacker won't get much help from CRT (Mersenne primes are particularly good).
2. Index calculus works much the same as it does in $GF(p)$. In addition to trying to solve the discrete logs of a set of small primes (much smaller than $p$), you want to include some low degree polynomials to your basis. Whenever you get a reduction modulo the polynomial defining the field you test whether the remainder factors completely as a product of the polynomials in the basis.