Should tower field implementations use the x^k element representation?

Question

I'm working on a friendly tower finite field implementation for educational purposes. The library should allow easy building of tower fields from smaller ones - a user may define $\mathbb F_q$ and then build a tower field such as $\mathbb F_q \rightarrow \mathbb F_{q^k} \rightarrow \mathbb F_{(q^k)^m}$ and add/multiply inside the constructed field.

My initial plan was to reduce polynomial operations in tower at level $n$ to polynomial operations at level $n-1$. For example, in $\mathbb F_{(q^k)^m}$, elements are polynomials of degree at most $m-1$ with coefficients being polynomials of degree at most $k-1$. Element addition/multiplication at certain tower level would reduce to addition/multiplication at one level below.

Now, "Finite Fields for Computer Scientists and Engineers" by McEliece shows how a mapping between polynomial elements and their multiplicative cyclic group representation. It appears show an automorphism: $\mathbb F_{2^3}$ polynomials are mapped into $x^k$ and back, and it shows that it is easier to do multiplication in the field that way. My understanding is that this indeed is the case, but then addition becomes more complicated, so we can't just keep the finite field elements in that format.

The question here is - is the representation used in the picture commonly used in practice in finite field implementations and why/in which scenarios? Or just representing field elements with polynomial coefficients is the usual way to go?

Answer 1

This approach is known as the generator-based representation of finite fields and essentially relies on representing each element using its discrete logarithm. This means that for larger base fields, switching to this representation involves solving a discrete logarithm which is inefficient and potentially infeasible.

Even if we forego conversion from other representations of the field, as you note there are difficulties in adding numbers that use this representation. In practice people implement addition using a look-up table for the Zech logarithm, but the computation of this look-up table involves multiple discrete logarithm computations which are again infeasible for large base fields.

I don't know whether recent work by Joux and Granger around solving discrete logarithms in small characteristic fields changes this analysis significantly, but historically it has not been as efficient as polynomial basis representation for large fields.

Answer 2

is the representation used in the picture (where field multiplication uses a log table) commonly used in practice in finite field implementations and why/in which scenarios?

This representation has one main drawback: as is, it uses memory growing (slightly more than) linearly with the field size. It's not directly usable (thus not directly used) for e.g. Elliptic Curve Cryptography with curves in a finite field of cryptographically relevant size, which must have at least like $2^{160}$ elements. The only way I see to avoid or reduce the huge table is to solve the DLP for the operands of a multiplication. That's going to be a speed/space compromize, and won't scale to fields of size relevant to asymmetric cryptography.

This representation is sometime used for small field size. It's often used to precompute the AES S-table. It can be used in the rest of the algorithm, though that's less common.

In the question's context of tower fields, this representation would be usable for the lower field $\mathbb F_{q^k}$ of $\mathbb F_{\left(q^k\right)^m}$ when $q^k$ is below some limit in the millions.