Obtaining Specified Irreducible Polynomials over Finite Fields
Solomon W. Golomb · SIAM Journal on Algebraic and Discrete Methods · 1980
In numerous applications, it is necessary to find an irreducible polynomial $f( x )$ of degree n over $GF( q )$ whose roots are primitive dth roots of unity. (Here d must divide $q^n - 1$.) Let $\alpha$ be one such root. A direct method is to write \[ f ( x ) = \prod\limits_{i = 0}^{n - 1} {\left( x - \alpha^{q^i } \right)} = \sum\limits_{j = 0}^n {( - 1 )} ^j C_j x^{n - j} ,\] where $C_0 = 1$ and all $C_j $ are in $GF ( q )$. Explicitly, $C_j $ is the sum of all powers of $\alpha $ whose exponents, written as n-digit numbers in base q, look like binary numbers of weight j. Formulas for the number of such polynomials $f ( x )$ are given, several computational shortcuts exploiting properties of cyclotomic polynomials are noted, and numerous illustrative examples are presented.