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 E. Collins (1967), Unpublished communication.
- 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 E. Knuth (1967), Unpublished communication. E. Knuth (1969), The Art of Computer Programming. Vol. II: Seminumerical Algorithms, Addison-Wesley, Reading, Mass., 1969.
- 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 P. F. Swinnerton-Dyer (1969), Unpublished communication. L. van der Waerden (1931), Moderne Algebra, Springer, Berlin, 1931; English transi., Ungar, New York, 1949. MR 10, 587. Welch (1969), Unpublished communication.
- Hans Zassenhaus, On Hensel factorization. I, J. Number Theory 1 (1969), 291–311. MR 242793, DOI 10.1016/0022-314X(69)90047-X
Additional Information
- © Copyright 1970 American Mathematical Society
- Journal: Math. Comp. 24 (1970), 713-735
- MSC: Primary 12.25; Secondary 94.00
- DOI: https://doi.org/10.1090/S0025-5718-1970-0276200-X
- MathSciNet review: 0276200