Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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

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{displaymath}\begin{array}{*{20}{c}} {q = 2:d = 20,{d_1} = 18,} \hfill & {... ...= {3^2}:d = 9,} \hfill & {q = 19:d = 7.} \hfill \\ \end{array} \end{displaymath}

On a microfiche card with this note, selected results from the above appear as Table I-Table IV as follows:

\begin{displaymath}\begin{array}{*{20}{c}} {q = 2:d = 20,{d_1} = 18,} \hfill & {... ... = 8,} \hfill & {q = 5:d = 5,{d_1} = 5.} \hfill \\ \end{array} \end{displaymath}

As evidenced by these tables, there does not necessarily exist a prime trinomial of given degree n over arbitrary $ {\text{GF}}(q)$.

References [Enhancements On Off] (What's this?)

  • [1] J. T. B. BEARD, JR., "Computing in $ {\text{GF}}(q)$," Math. Comp., v. 28, 1974, pp. 1159-1166. MR 0352058 (50:4546)
  • [2] J. T. B. BEARD, JR. & K. I. WEST, "Some primitive polynomials of the third kind," Math. Comp., v. 28, 1974, pp. 1166-1167. MR 0366879 (51:3125)
  • [3] J. T. B. BEARD, JR. & K. I. WEST, "Factorization tables for $ {x^n} - 1$ over $ {\text{GF}}(q)$," Math. Comp., v. 28, 1974, pp. 1167-1168. MR 0364196 (51:451)
  • [4] J. T. B. BEARD, JR. & K. I. WEST, "Factorization tables for binomials over $ {\text{GF}}(q)$," Math. Comp. (Submitted.)
  • [5] E. R. BERLEKAMP, Algebraic Coding Theory, McGraw-Hill, New York, 1968. MR 38 #6873. MR 0238597 (38:6873)
  • [6] R. J. McELIECE, "Factorization of polynomials over finite fields," Math. Comp., v. 23, 1969, pp. 861-867. MR 41 #1694a. MR 0257039 (41:1694a)
  • [7] O. ORE, "Contributions to the theory of finite fields," Trans. Amer. Math. Soc., v. 36, 1934, pp. 243-274. MR 1501740
  • [8] N. ZIERLER & J. BRILLHART, "On primitive trinomials $ (\operatorname{Mod}\;2)$," Information and Control, v. 13, 1968, pp. 541-554. MR 38 #5750. MR 0237468 (38:5750)


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-76-99670-8
Keywords: Factorization, Galois field, trinomial, Euler $ \Phi $-function, numerical exponent, q-polynomial
Article copyright: © Copyright 1976 American Mathematical Society

American Mathematical Society