HP Labs Technical Reports

Table of Low-Weight Binary Irreducible Polynomials

Seroussi, Gadiel

HPL-98-135

Keyword(s): finite fields; irreducible polynomials

Abstract: A table of low-weight irreducible polynomials over the finite field F(sub2) is presented. For each integer n in the range 2 (greater than equal) n (greater than equal to ) 10,000, a binary irreducible polynomial f(x) of degree n and minimum posible weight is listed. Among those of minimum weight, the polynomial listed is such that the degree of f(x) - x(super n) is lowest (similarly, subsequent lower degrees are minimized in case of ties). All the polynomials listed are either trinomials or pentanomials. The general question of whether an irreducible polynomial of weight at most 5 (or any other fixed odd weight w (greater than equal to) 5) exists for every value of n is an open one. Low-weight irreducibles are useful when implementing the arithmetic of the finite field F(sub 2n), as the number of operations in the reduction of the product of two polynomials of degree n - 1 modulo an irreducible of degree n and weight w is proportional to (w 1)n.

15 Pages

Back to Index