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
xn-1 and the subtrace is the
coefficient of xn-2.
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(2n)
are defined to be the coefficients of xn-1
and xn-2,
respectively, in the polynomial
PROD {i=0...n-1}
( x + \beta2i ).
We also derive an explicit formula for the number of elements of
GF(2n) of given trace and subtrace.
Moreover, a new two equation Möbius-type 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) 31-64.
-
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 FFA2000-0002.
- 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,552--555;
translation in Soviet Math. Dokl. 42 (1991), no. 1, 45--48
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 Hewlett-Packard 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) 265-279.
-
J. L. Yucas and G. Mullen,
Self-Reciprocal Irreducible Polynomials Over Finite Fields,
Designs, Codes, and Cryptography, 33 (2004) 275-281.
Back to list of publications.