Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm implementing some code for the Galois field $\mathrm{GF}(2^{16})$. Which irreducible polynomial do you recommend that I use?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
Of course, if you don't do discrete log tables, then there is no compelling reason to use a primitive polynomial. But I would recommend doing that. For implementing multiplication of two elements of the field a couple of table look-ups (and a modular addition of discrete logs) is a good approach. –  Jyrki Lahtonen Oct 7 '11 at 11:35
2  
"...you may also consider the primitive polynomial used by MATLAB. I ... cannot tell, which polynomial they use." - Jyrki, apparently it's $x^{16}+x^{12}+x^3+x+1$... so, exactly what you gave. ;) –  J. M. Oct 7 '11 at 11:46

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.

share|improve this answer
    
+1 What a nice idea! (The doubled-up LUT) I know a dude who needs to do a little bit of coding sometime soon. When I needed this the most, I was battling against the 64 kByte barrier of a segment, so then this might not have been best. But that is a thing of the past, now. Of course, this won't necessarily do away with all the modular arithmetic, as sometimes one may want to compute powers using the log table - and doubling the range won't do then. But I often use a LUT of Frobenius automorphisms to aid that anyway, and then this trick will help very much. –  Jyrki Lahtonen Oct 7 '11 at 13:02
    
And to get a multiplicative inverse you can take a suitable 2s complement of the logarithm, and offset that by a fixed amount (that I can't be bothered to compute right now...) –  Jyrki Lahtonen Oct 7 '11 at 13:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.