Finding irreducible polynomials over GF(2) with the fewest terms

Question

I'm investigating an idea in cryptography that requires irreducible polynomials with coefficients of either 0 or 1 (e.g. over GF[2]). Essentially I am mapping bytes to polynomials. For this reason, the degree of the polynomial will always be an integer multiple of 8.

I would like to build a table of such irreducible polynomials for various degrees (e.g. degrees from 8, 16, 24, ..., 1024). Because there are multiple irreducible polynomials for a given degree, I'd like the one with the fewest number of terms since I will hard code the non-zero terms. For example, for degree 16, both of these polynomials are irreducible:

$x^{16} + x^{14} + x^{12} + x^7 + x^6 + x^4 + x^2 + x + 1$

and

$x^{16} + x^5 + x^3 + x + 1$

Obviously, the latter one is preferred because it requires less space in code and is more likely to be right (e.g. that I wouldn't have made a copy/paste error).

Furthermore, I've noticed that to at least degree 1024 where the degree is a multiple of 8, there are irreducible polynomials of the form:

$x^n + x^i + x^j + x^k + 1$ where $n = 8*m$ and $0 < i,j,k < 25$

Is there an good algorithmic way of finding these polynomials (or ones that have even fewer terms)? Again, the purpose is to keep the non-zero terms in a look-up table in code.

Thanks in advance for any help!

UPDATE:

This Mathematica code generates all pentanomials for degrees that are multiples of 8 up to degree 1024:

IrreducibleInGF2[x_] := IrreduciblePolynomialQ[x, Modulus -> 2]

ParallelTable[
 Select[
   Sort[
    Flatten[
        Table[
           x^n + x^a + x^b + x^c + 1, 
           {a, 1, Min[25, n - 1]}, {b, 1, a - 1}, {c, 1, b - 1}
             ]
           ]
       ], 
       IrreducibleInGF2, 1], 
       {n, 8, 1024, 8}]

(I sorted the list of polynomials to make sure I always got the one with the overall smallest degrees first). However, it takes quite a bit of time to run. For example, it took over 26 minutes for the case of $x^{984} + x^{24} + x^9 + x^3 + 1$ .

UPDATE #2

The HP paper "Table of Low-Weight Binary Irreducible Polynomials" has been incredibly helpful. It lists up to $x^{10000}$ and reiterates a proof by Swan that there are no trinomials when the degree is a multiple of 8 (which matches my findings). I've spot checked that their results match mine up to $x^{1024}$ so I'll just need to double check their results up to 10000 which should be much easier than finding them myself.

Answer 1

According to a paper "Optimal Irreducible Polynomials for $GF(2^m)$ Arithmetic" by M. Scott, "it is in practise always possible to chooose as an irreducible polynomial either a trinomial... or a pentanomial." [talk slides] [PDF link]

In random number generators irreducible trinomials of various degrees with three nonzero binary coefficients are associated with the names Tausworthe-Lewis-Payne.

Added: It has been known since Gauss that there are lots of irreducible polynomials over a finite field, basically the analog of the Prime Number Theorem for such polynomials. Among the $2^m$ (monic) polynomials over Z/2Z of degree $m$, approximately $1/m$ of them are irreducible.

We can eliminate the possibility of first degree factors by inspection, for divisibility by $x$ or $x+1$ would imply respectively a zero constant term or an even number of nonzero terms in the polynomial. So the first case to test for irreducibility is the trinomials of degree $m$. With leading and constant coefficients accounting for two of the three nonzero terms, there are but $m-1$ possibilities to test, and by symmetry of $x$ → $1/x$ substitution, we can restrict the middle terms to degree ≤ $m/2$.

If none of those pan out, we have the richer supply of pentanomials to test. Indeed you seem to have hit upon a seam of cases where trinomials will never work out, namely degree $m$ a multiple of 8 [PS] (Swan, 1962).

The work then comes down to testing all the $\binom{m-1}{3}$ binary pentanomials $p(x)$ until we find one that's irreducible. Your application might make other conditions, perhaps similar to those considered in Scott's paper above, attractive. Given the modest degrees you are working with, trial division (taking $p(x) \; mod \; q(x)$ for all $q(x)$ of degree ≤ $m/2$) should be fast enough. [Remember, we shouldn't have to test more than O(m) possibilities before we find success.]

There is a fancier way [PDF] to test polynomials for irreducibility over GF(2). A necessary condition for binary polynomial $p(x)$ to be irreducible over $GF(2)$ is that:
$$x^{2^m} = x \mod p(x)$$

In fact Gauss showed for prime q that $x^{q^m} - x$ is precisely the product of all monic irreducible polynomials over $GF(q)$ whose degrees divide $m$. [From this he deduced the count of monic irreducible polynomials of degree exactly $m$ is asymptotically $q^m/m$ as $m \rightarrow \infty$.]

For $q = 2$ it follows that if $p(x)$ is irreducible of degree $m$, it divides $x^{2^m} - x$ over $GF(2)$, i.e. the congruence above.

Rubin (1980) proposed a necessary and sufficient test for irreducibility, combining the above with some additional steps to rule out the possibility that $p(x)$ might be the product of some irreducible factors whose degrees properly divide $m$. [While the degrees of the irreducible factors would naturally sum to $m$, having all the irreducible factors' degrees divide $m$ would be somewhat special, unless of course there is only one factor.]

The additional "sufficiency" steps are to check for each prime factor $d_i$ of $m$ that: $$GCD(x^{2^{m/d}} - x, p(x)) = 1$$

That is, if $p(x)$ were to have an irreducible factor of degree $k$ properly dividing $m$, it would crop up when taking the gcd of $x^{2^{m/d}} - x$ and $p(x)$ if $k$ divides $m/d$.

Since then a lot of ingenuity has been applied to efficiently doing these steps. Of course the necessary condition lends itself to repeated squaring, computing $x^{2^{k+1}} = (x^{2^k})^2$ mod $p(x)$, for $k$ up to $m-1$. We can take advantage here of the fact that the multiplication we're doing is a squaring and advantage of the sparsity of our $p(x)$ as a pentanomial when doing reduction mod $p(x)$.

As the report by Brent of work with Zimmerman (linked above) points out, this repeated squaring gives with each (fairly inexpensive step) linear progress toward the "exponent of the exponent" $m$. There is also a way to progress farther with greater computational effort by modular composition.

That is, suppose we've already arrived at: $$f(x) = x^{2^k} \mod p(x)$$ and $$g(x) = x^{2^j} \mod p(x)$$ Then: $$f(g(x)) = x^{2^{k+j}} \mod p(x)$$

Thus composition of two polynomials $f(x)$ and $g(x)$ mod $p(x)$ can replace a number of repeated squaring steps. But composition mod $p(x)$ is more expensive than squaring or even than multiplication generally mod $p(x)$. So as Brent points out, practical advantage for using modular composition lies at the final stage(s) of evaluating the necessary condition. E.g. at the end one modular composition might replace $m/2$ repeated squarings.

As far as the "sufficiency" conditions go, Gao and Panario outlined an improvement over a naive implementation of Rubin's tests in this 1997 paper [PDF], basically sequencing the gcd computations in an expedient order.

Answer 2

The abstract of the following paper indicates that it may be of interest:

An Improved Method for the Table Lookup Multiplication Algorithm over $\rm\: GF(2^m\:)$.

Author: Hadama Yoichi (Kobe Univ., Graduate School of Sci. and Technol., JPN)
Nakamura Daisuke (Kobe Univ., Graduate School of Sci. and Technol., JPN)
Hirotomo Masanori (Hyogojohokyoikukiko)
Morii Masakatsu (Kobe Univ., Fac. Engineering, JPN)

Journal Title: IEIC Technical Report (Institute of Electronics, Information and Communication Engineers)

Journal Code: S0532B; ISSN:0913-5685 VOL.106;NO.175(ISEC2006 9-39);PAGE.95-102(2006)

Abstract: As effective arithmetic methods in the finite field $\rm\: GF(2^m\:)$, M.A. Hasan has presented a look-up table-based algorithm for $\rm\: GF(2^m\:)$ multiplication. In Hasan's method, the number of memory access and the table size are depend on the form of the irreducible polynomial which is used in the $\rm\: GF(2^m\:)$ multiplication. In this paper, we propose a lookup-up table-based algorithm which can be performed as an efficient $\rm\: GF(2^m\:)$ multiplication using the irreducible polynomial which has $m$ degree and $m$ terms. In this method, the algorithm is performed as the multiplication modulo quadnomial which is obtained by the irreducible polynomial which has m degree and m terms. Using this method, the number of memory access and the table size in the algorithm is smaller than that in Hasan's method, and $\rm\: GF(2^m\:)$ multiplication is faster than Hasan's method.