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)$," Math. Comp. (Submitted.)
- 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
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