Computing in $\textrm {GF} (q)$
HTML articles powered by AMS MathViewer
- by Jacob T. B. Beard PDF
- Math. Comp. 28 (1974), 1159-1166 Request permission
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
- A. Adrian Albert, Fundamental concepts of higher algebra, 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 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 10.1090/S0002-9947-1952-0051869-9
- H. Davenport, Bases for finite fields, J. London Math. Soc. 43 (1968), 21β39. MR 227144, DOI 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 10.1090/S0002-9947-1934-1501740-7
Additional Information
- © Copyright 1974 American Mathematical Society
- 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