How to calculate log or exp of a value in GF(2^n) using log/exp table of GF((2^k)^m) where n=k*m?

Question

Consider Galois fields $\mathbb{F}_{2^n}$ and $\mathbb{F}_{2^k}$, where $n=km$, and $\mathbb{F}_{2^k}$ is a ground field of $\mathbb{F}_{2^n}$.

I’d appreciate pointers to papers or suggestions on:

1. How to find $\log(a)$ and $\exp(a)$ for $a\in \mathbb{F}_{2^n}$, given log/exp look-up tables of $\mathbb{F}_{2^k}$?
2. How to convert the values from $\mathbb{F}_{2^n}$ to $\mathbb{F}_{(2^k)^m}$ .

Specifically I need solution for n=16 (with any combination of integer m and k, e.g. k=8, m=2) such that amount of calculations used for conversion is minimal. Generator polynomials for all three fields can be assumed to be known, for example for case of n=16, k=8, m=2:

 - GF(2^16):     x^16 + x^5 + x^3 + x^2 + 1
 - GF(2^8):      x^8  + x^4 + x^3 + x^2 + 1
 - GF((2^8)^2):  x^2  + 3x  + 1

Additional background info: Generally I have log and exp look-up tables for GF(2^n) and can avoid the conversion problem all together, but 2^n tables don't fit into memory-constrained CPU I’m using. Thus i'm interested to calculate log and exp of GF(2^16) using log/exp tables of GF(2^8) or GF(2^4). I came across this paper (http://web.eecs.utk.edu/~plank/plank/papers/UT-CS-13-717.pdf), but it explicitly says that GF(2^km) is not identical to GF((2^k)^m), but doesn’t offer a way to convert between the two: the result of multiplication using ground and extension fields doesn’t match the multiplication result using any other method (presumably because the composite field is not identical to the original field).

Thanks in advance for any help

Answer 1

Efficient algorithms to compute in finite fields are based on Conway polynomials. Such algorithms are implemented in several computer algebra systems, for example in GAP. For details, see e.g. the chapter on finite fields in the GAP Reference Manual. In particular, GAP can compute very efficiently in the field ${\rm GF}(2^{16})$ you ask about -- to cite the GAP Reference Manual:

GAP can represent elements of all finite fields ${\rm GF}(p^d)$ such that either (1) $p^d \leq 65536$ (in which case an extremely efficient internal representation is used); (2) $d = 1$, (in which case, for large $p$, the field is represented using the machinery of residue class rings (see Section 14.5) or (3) if the Conway polynomial of degree $d$ over the field with $p$ elements is known, or can be computed (see ConwayPolynomial (59.5-1)).