HP Labs Technical Reports
Click here for full text:
Table of LowWeight Binary Irreducible Polynomials
Seroussi, Gadiel
HPL98135
Keyword(s): finite fields; irreducible polynomials
Abstract: A table of lowweight 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. Lowweight 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
