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. Adrian Albert,*Fundamental concepts of higher algebra*, The University of Chicago Press, Chicago, Ill., 1958. MR**0098735****[2]**J. T. B. Beard Jr.,*Matrix fields over prime fields*, Duke Math. J.**39**(1972), 313–321. MR**0313269****[3]**E. R. Berlekamp,*Factoring polynomials over large finite fields*, Math. Comp.**24**(1970), 713–735. MR**0276200**, https://doi.org/10.1090/S0025-5718-1970-0276200-X**[4]**Elwyn R. Berlekamp,*Algebraic coding theory*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968. MR**0238597****[5]**L. Carlitz,*Primitive roots in a finite field*, Trans. Amer. Math. Soc.**73**(1952), 373–382. MR**0051869**, https://doi.org/10.1090/S0002-9947-1952-0051869-9**[6]**H. Davenport,*Bases for finite fields*, J. London Math. Soc.**43**(1968), 21–39. MR**0227144**, https://doi.org/10.1112/jlms/s1-43.1.21**[7]**Oystein Ore,*Contributions to the theory of finite fields*, Trans. Amer. Math. Soc.**36**(1934), no. 2, 243–274. MR**1501740**, https://doi.org/10.1090/S0002-9947-1934-1501740-7

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