Computing in $\textrm {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 Free Access

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.

- A. Adrian Albert,
*Fundamental concepts of higher algebra*, The University of Chicago Press, Chicago, Ill., 1958. MR**0098735** - J. T. B. Beard Jr.,
*Matrix fields over prime fields*, Duke Math. J.**39**(1972), 313β321. MR**313269** - E. R. Berlekamp,
*Factoring polynomials over large finite fields*, Math. Comp.**24**(1970), 713β735. MR**276200**, DOI https://doi.org/10.1090/S0025-5718-1970-0276200-X - Elwyn R. Berlekamp,
*Algebraic coding theory*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968. MR**0238597** - L. Carlitz,
*Primitive roots in a finite field*, Trans. Amer. Math. Soc.**73**(1952), 373β382. MR**51869**, DOI https://doi.org/10.1090/S0002-9947-1952-0051869-9 - H. Davenport,
*Bases for finite fields*, J. London Math. Soc.**43**(1968), 21β39. MR**227144**, DOI https://doi.org/10.1112/jlms/s1-43.1.21 - 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

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

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

Additional Information

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