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
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.

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

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

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