Computing in

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 Free Access

Abstract | References | Similar Articles | Additional Information

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

**[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**

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