Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Computing in $ {\rm GF}\,(q)$


Author: Jacob T. B. Beard
Journal: Math. Comp. 28 (1974), 1159-1166
MSC: Primary 12C05; Secondary 12-04
DOI: https://doi.org/10.1090/S0025-5718-1974-0352058-9
MathSciNet review: 0352058
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper gives an elementary deterministic algorithm for completely factoring any polynomial over $ {\text{GF}}(q),q = {p^d}$, criteria for the identification of three types of primitive polynomials, an exponential representation for $ {\text{GF}}(q)$ which permits direct rational calculations in $ {\text{GF}}(q)$ as opposed to modular arithmetic over $ {\text{GF}}[p,x]$, and a matrix representation for $ \overline {{\text{GF}}} (p)$ which admits computer computations. The third type of primitive polynomial examined permits the given representation of $ {\text{GF}}(q)$ to display a primitive normal basis over $ {\text{GF}}(p)$. The techniques developed require only the usual addition and multiplication of square matrices over $ {\text{GF}}(p)$. Partial tables from computer programs based on certain of these results will appear in later papers.


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

  • [1] A. A. ALBERT, Fundamental Concepts of Higher Algebra, Univ. of Chicago Press, Chicago, Ill., 1958. MR 20 #5190. MR 0098735 (20:5190)
  • [2] J. T. B. BEARD, JR., "Matrix fields over prime fields," Duke Math. J., v. 39, 1972, pp. 313-322. MR 0313269 (47:1824)
  • [3] E. R. BERKLEKAMP, "Factoring polynomials over large finite fields," Math. Comp., v. 24, 1970, pp. 713-735. MR 34 #1948. MR 0276200 (43:1948)
  • [4] E. R. BERLEKAMP, Algebraic Coding Theory, McGraw-Hill, New York, 1968. MR 38 #6873. MR 0238597 (38:6873)
  • [5] L. CARLITZ, "Primitive roots in a finite field," Trans. Amer. Math. Soc., v. 73, 1952, pp. 373-382. MR 14, 539. MR 0051869 (14:539a)
  • [6] H. DAVENPORT, "Bases for finite fields," J. London Math. Soc., v. 43, 1968, pp. 21-39; ibid., v. 44, 1969, p. 378. MR 37 #2729; 38 #2127. MR 0227144 (37:2729)
  • [7] O. ORE, "Contributions to the theory of finite fields," Trans. Amer. Math. Soc., v. 36, 1934, pp. 243-274. MR 1501740

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 12C05, 12-04

Retrieve articles in all journals with MSC: 12C05, 12-04


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1974-0352058-9
Keywords: Factorization, arithmetic in finite fields, irreducibility criterion, primitive polynomials, primitive normal bases, Euler function, exponent, linear polynomial, algebraic closure
Article copyright: © Copyright 1974 American Mathematical Society

American Mathematical Society