Irreducible polynomial of $\mathrm{GF}(2^{16})$

This table contains a list of primitive polynomials written in octal. The first entry in that table for $GF(2^{16})$ is $$ 210013_8=x^{16}+x^{12}+x^3+x+1. $$ IOW each octal digit gives 3 coefficients of the polynomial, the least significant bits correspond to lowest degree terms.

For many a hardware implementation a low weight polynomial is better - particularly for generating $m$-sequences, so you may want to support those. For reasons of compatibility / portability / independent verification on a different program you may also consider the primitive polynomial used by Matlab. I no longer have a copy on my laptop, so cannot tell, which polynomial they use.

If you decide to generate discrete logarithm tables as part of your program initialization, then you can support several primitive polynomials! The logic of the construction of the said table (and its inverse table, if judged useful) is independent from the exact form of the primitive polynomial.


I would recommend giving some thought to a different alternative. GF$(2^{16})$ is a degree-$2$ extension field of GF$(2^8)$, that is, each element of GF$(2^{16})$ can be represented as a polynomial $a_0 + a_1z$ where $a_0, a_1 \in \text{GF}(2^8)$, and so arithmetic operations in GF$(2^{16})$ become polynomial arithmetic operations in GF$(2^8)$. While the latter would take more time than the log table approach that can be used directly in GF$(2^{16})$, extensive subroutine libraries have been developed already for arithmetic in GF$(2^8)$ and you might be able to use them to save development effort and cost.

I will also suggest that the modular addition of discrete logarithms that @Jyrki has recommended be modified a little to avoid modular arithmetic, and also the unstated need to check if a multiplicand is $0$ before looking up its logarithm. By defining a suitable "value" for the logarithm of $0$, multiplication can be implemented via two table lookups, an addition, and another table lookup to get the product, without the need for testing the operands or for modular reduction following the addition. This is much faster. See here for ideas as to what can be done in this regard.