Factoring polynomials over large finite fields

Berlekamp, E. R.

doi:10.1090/S0025-5718-1970-0276200-X

Factoring polynomials over large finite fields
HTML articles powered by AMS MathViewer

by E. R. Berlekamp PDF

Math. Comp. 24 (1970), 713-735 Request permission

Abstract:

This paper reviews some of the known algorithms for factoring polynomials over finite fields and presents a new deterministic procedure for reducing the problem of factoring an arbitrary polynomial over the Galois field ${\text {GF}}({p^m})$ to the problem of finding the roots in ${\text {GF}}(p)$ of certain other polynomials over ${\text {GF}}(p)$. The amount of computation and the storage space required by these algorithms are algebraic in both the degree of the polynomial to be factored and the logarithm of the order of the finite field. Certain observations on the application of these methods to the factorization of polynomials over the rational integers are also included.

References

E. R. Berlekamp, Factoring polynomials over finite fields, Bell System Tech. J. 46 (1967), 1853–1859. MR 219231, DOI 10.1002/j.1538-7305.1967.tb03174.x
Elwyn R. Berlekamp, Algebraic coding theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968. MR 0238597
E. R. Berlekamp, H. Rumsey, and G. Solomon, On the solution of algebraic equations over finite fields, Information and Control 10 (1967), 553–564. MR 230706
Garrett Birkhoff and Saunders Mac Lane, A survey of modern algebra, 3rd ed., The Macmillan Company, New York; Collier Macmillan Ltd., London, 1965. MR 0177992
Alfred Brauer and Gertrude Ehrlich, On the irreducibility of certain polynomials, Bull. Amer. Math. Soc. 52 (1946), 844–856. MR 17750, DOI 10.1090/S0002-9904-1946-08655-3
W. S. Brown and R. L. Graham, An irreducibility criterion for polynomials over the integers, Amer. Math. Monthly 76 (1969), 795–797. MR 249407, DOI 10.2307/2317870
D. A. Burgess, On character sums and primitive roots, Proc. London Math. Soc. (3) 12 (1962), 179–192. MR 132732, DOI 10.1112/plms/s3-12.1.179
George E. Collins, Computing multiplicative inverses in $\textrm {GF}(p)$, Math. Comp. 23 (1969), 197–200. MR 242345, DOI 10.1090/S0025-5718-1969-0242345-5
Walter Gautschi, On inverses of Vandermonde and confluent Vandermonde matrices, Numer. Math. 4 (1962), 117–123. MR 139627, DOI 10.1007/BF01386302
Marshall Hall Jr., Combinatorial theory, Blaisdell Publishing Co. [Ginn and Co.], Waltham, Mass.-Toronto, Ont.-London, 1967. MR 0224481

The Art of Computer Programming

Seminumerical Algorithms

Daniel B. Lloyd, Factorization of the General Polynomial by Means of Its Homomorphic Congruential Functions, Amer. Math. Monthly 71 (1964), no. 8, 863–870. MR 1532901, DOI 10.2307/2312393
Štefan Schwarz, On the reducibility of polynomials over a finite field, Quart. J. Math. Oxford Ser. (2) 7 (1956), 110–124. MR 96679, DOI 10.1093/qmath/7.1.110
Johanan Schönheim, Formules pour résoudre la congruence $x^{2}\equiv a (\mod P)$ dans des cas encore inconnus et leur application pour déterminer directement des racines primitives de certains nombres premiers, Acad. R. P. Romîne. Fil. Cluj. Stud. Cerc. Mat. Fiz. 7 (1956), no. 1-4, 51–58 (Romanian, with French and Russian summaries). MR 95798

Moderne Algebra

10

Hans Zassenhaus, On Hensel factorization. I, J. Number Theory 1 (1969), 291–311. MR 242793, DOI 10.1016/0022-314X(69)90047-X