The Number of Irreducible Polynomials over GF(2) with Given
Trace and Subtrace
Kevin Cattell,
Department of Computer Science,
University of Victoria, Canada.
C. Robert Miers,
Department of Mathematics and Statistics,
University of Victoria, Canada.
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
Joe Sawada,
Department of Computer Science,
University of Victoria, Canada.
Micaela Serra,
Department of Computer Science,
University of Victoria, Canada.
Abstract:
The trace of a degree n polynomial p(x)
over GF(2) is the coefficient of
x^{n1} and the subtrace is the
coefficient of x^{n2}.
We derive an explicit formula for the number of irreducible
degree n polynomials over GF(2) that have a given trace
and subtrace.
The trace and subtrace of an element \beta in GF(2^{n})
are defined to be the coefficients of x^{n1}
and x^{n2},
respectively, in the polynomial
PROD {i=0...n1}
( x + \beta^{2i} ).
We also derive an explicit formula for the number of elements of
GF(2^{n}) of given trace and subtrace.
Moreover, a new two equation Möbiustype inversion formula
is proved.

The postscript file is 289,172 bytes,
the dvi file (not yet) is ??? bytes.

Appears in Journal of Combinatorial Mathematics and Combinatorial
Computing, 47 (November 2003) 3164.

The story of this paper:
 June 1999 paper submitted to the Canadian Journal of Mathematics.
 September 1999 received the following from CJM: "..."
 December 16, 1999 paper submitted to Finite Fields
and Their Applications; they gave it number FFA20000002.
 February 14, 2001 received the following single referee
report from FFA:
"I have to recommend that this paper be rejected for the following
reason. The results have been proved more succinctly and more
generally in the following short paper. Kuz'min, E.N. A class of
irreducible polynomials over a finite field.
(Russian) Dokl. Akad. Nauk SSSR 313 (1990), no. 3,552555;
translation in Soviet Math. Dokl. 42 (1991), no. 1, 4548
MR 92g:11118."

February 2002, submitted yet again. February 26, 2002:
Accepted to appear in Journal of Combinatorial Mathematics and
Combinatorial Computing. Yipee!

Kevin Cattell now works for HewlettPackard in Santa Rosa, California.

There are some information pages on COS about these numbers.

The numbers now have numbers in Sloane's database of integer
sequences....
Selected papers that refer to this paper.

J. L. Yucas and G. Mullen, Irreducible polynomials over GF(2)
with prescribed coefficients,
Discrete Mathematics, 274 (2004) 265279.

J. L. Yucas and G. Mullen,
SelfReciprocal Irreducible Polynomials Over Finite Fields,
Designs, Codes, and Cryptography, 33 (2004) 275281.
Back to list of publications.