Table of Low-Weight Binary Irreducible Polynomials

Seroussi, Gadiel

HP Development Company

关键词: finite fields;    irreducible polynomials;   

RP-ID  :  HPL-98-135

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

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