Factorization tables for trinomials over $\mathrm {GF}(q)$

Authors:
Jacob T. B. Beard, Jr. and Karen I. West

Journal:
Math. Comp. **30** (1976), 179-183

DOI:
https://doi.org/10.1090/S0025-5718-76-99670-8

MathSciNet review:
0392940

Full-text PDF Free Access

Abstract | References | Additional Information

Abstract: Tables placed in the UMT file give the complete factorization over ${\text {GF}}(q),q = {p^a}$, of each trinomial $T(x)$ of degree $n, 2 \leqslant n \leqslant d$, as below, together with the generalized Euler $\Phi$-function whenever $T(x)$ is not prime and $\Phi (T(x)) < {10^8}$. In addition, the numerical exponent and *q*-polynomial is given for each $T(x)$ whenever $2 \leqslant n \leqslant {d_1}$. \[ \begin {array}{*{20}{c}} {q = 2:d = 20,{d_1} = 18,} \hfill & {q = 5:d = 15,{d_1} = 8,} \hfill \\ {q = {2^2}:d = 16,{d_1} = 10,} \hfill & {q = 7:d = 10,{d_1} = 7,} \hfill \\ {q = {2^3}:d = 9,{d_1} = 7,} \hfill & {q = 11:d = 7,} \hfill \\ {q = {2^4}:d = 8,} \hfill & {q = 13:d = 7,} \hfill \\ {q = 3:d = 18,{d_1} = 9,} \hfill & {q = 17:d = 7,} \hfill \\ {q = {3^2}:d = 9,} \hfill & {q = 19:d = 7.} \hfill \\ \end {array} \] On a microfiche card with this note, selected results from the above appear as Table I-Table IV as follows: \[ \begin {array}{*{20}{c}} {q = 2:d = 20,{d_1} = 18,} \hfill & {q = 3:d = 11,{d_1} = 9,} \hfill \\ {q = {2^2}:d = 8,{d_1} = 8,} \hfill & {q = 5:d = 5,{d_1} = 5.} \hfill \\ \end {array} \] As evidenced by these tables, there does not necessarily exist a prime trinomial of given degree *n* over arbitrary ${\text {GF}}(q)$.

- Jacob T. B. Beard Jr.,
*Computing in ${\rm GF}\,(q)$*, Math. Comp.**28**(1974), 1159β1166. MR**352058**, DOI https://doi.org/10.1090/S0025-5718-1974-0352058-9 - Jacob T. B. Beard Jr. and Karen I. West,
*Some primitive polynomials of the third kind*, Math. Comp.**28**(1974). MR**366879**, DOI https://doi.org/10.1090/S0025-5718-1974-0366879-X - Jacob T. B. Beard Jr. and Karen I. West,
*Factorization tables for $x^{n}-1$ over ${\rm GF}\,(q)$*, Math. Comp.**28**(1974). MR**364196**, DOI https://doi.org/10.1090/S0025-5718-1974-0364196-5
J. T. B. BEARD, JR. & K. I. WEST, "Factorization tables for binomials over ${\text {GF}}(q)$," - Elwyn R. Berlekamp,
*Algebraic coding theory*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968. MR**0238597** - Robert J. McEliece,
*Factorization of polynomials over finite fields*, Math. Comp.**23**(1969), 861β867. MR**257039**, DOI https://doi.org/10.1090/S0025-5718-1969-0257039-X - Oystein Ore,
*Contributions to the theory of finite fields*, Trans. Amer. Math. Soc.**36**(1934), no. 2, 243β274. MR**1501740**, DOI https://doi.org/10.1090/S0002-9947-1934-1501740-7 - Neal Zierler and John Brillhart,
*On primitive trinomials $({\rm mod}\ 2)$*, Information and Control**13**(1968), 541β554. MR**237468**

*Math. Comp.*(Submitted.)

Additional Information

Keywords:
Factorization,
Galois field,
trinomial,
Euler <IMG WIDTH="20" HEIGHT="18" ALIGN="BOTTOM" BORDER="0" SRC="images/img18.gif" ALT="$\Phi$">-function,
numerical exponent,
<I>q</I>-polynomial

Article copyright:
© Copyright 1976
American Mathematical Society