Computing in
Author:
Jacob T. B. Beard
Journal:
Math. Comp. 28 (1974), 11591166
MSC:
Primary 12C05; Secondary 1204
MathSciNet review:
0352058
Fulltext 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
(20 #5190)
 [2]
J.
T. B. Beard Jr., Matrix fields over prime fields, Duke Math.
J. 39 (1972), 313–321. MR 0313269
(47 #1824)
 [3]
E.
R. Berlekamp, Factoring polynomials over large
finite fields, Math. Comp. 24 (1970), 713–735. MR 0276200
(43 #1948), http://dx.doi.org/10.1090/S0025571819700276200X
 [4]
Elwyn
R. Berlekamp, Algebraic coding theory, McGrawHill Book Co.,
New YorkToronto, Ont.London, 1968. MR 0238597
(38 #6873)
 [5]
L.
Carlitz, Primitive roots in a finite
field, Trans. Amer. Math. Soc. 73 (1952), 373–382. MR 0051869
(14,539a), http://dx.doi.org/10.1090/S00029947195200518699
 [6]
H.
Davenport, Bases for finite fields, J. London Math. Soc.
43 (1968), 21–39. MR 0227144
(37 #2729)
 [7]
Oystein
Ore, Contributions to the theory of finite
fields, Trans. Amer. Math. Soc.
36 (1934), no. 2,
243–274. MR
1501740, http://dx.doi.org/10.1090/S00029947193415017407
 [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. 313322. MR 0313269 (47:1824)
 [3]
 E. R. BERKLEKAMP, "Factoring polynomials over large finite fields," Math. Comp., v. 24, 1970, pp. 713735. MR 34 #1948. MR 0276200 (43:1948)
 [4]
 E. R. BERLEKAMP, Algebraic Coding Theory, McGrawHill, 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. 373382. MR 14, 539. MR 0051869 (14:539a)
 [6]
 H. DAVENPORT, "Bases for finite fields," J. London Math. Soc., v. 43, 1968, pp. 2139; 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. 243274. MR 1501740
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
12C05,
1204
Retrieve articles in all journals
with MSC:
12C05,
1204
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718197403520589
PII:
S 00255718(1974)03520589
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
