HP Labs Technical Reports
Click here for full text:
Table of Low-Weight Binary Irreducible Polynomials
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.
Back to Index