Factorization of multivariate polynomials over finite fields

Authors:
J. von zur Gathen and E. Kaltofen

Journal:
Math. Comp. **45** (1985), 251-261

MSC:
Primary 12E05; Secondary 11Y16, 68Q40

DOI:
https://doi.org/10.1090/S0025-5718-1985-0790658-X

MathSciNet review:
790658

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present a probabilistic algorithm that finds the irreducible factors of a bivariate polynomial with coefficients from a finite field in time polynomial in the input size, i.e., in the degree of the polynomial and log (cardinality of field). The algorithm generalizes to multivariate polynomials and has polynomial running time for densely encoded inputs. A deterministic version of the algorithm is also discussed, whose running time is polynomial in the degree of the input polynomial and the size of the field.

**[1]**Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman,*The design and analysis of computer algorithms*, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing; Addison-Wesley Series in Computer Science and Information Processing. MR**0413592****[2]**M. Ben-Or,*Probabilistic Algorithms in Finite Fields*, Proc. 22nd Sympos. Foundations Comp. Sci., IEEE, 1981, pp. 394-398.**[3]**E. R. Berlekamp,*Factoring polynomials over finite fields*, Bell System Tech. J.**46**(1967), 1853–1859. MR**219231**, https://doi.org/10.1002/j.1538-7305.1967.tb03174.x**[4]**E. R. Berlekamp,*Factoring polynomials over large finite fields*, Math. Comp.**24**(1970), 713–735. MR**276200**, https://doi.org/10.1090/S0025-5718-1970-0276200-X**[5]**W. S. Brown,*On Euclid’s algorithm and the computation of polynomial greatest common divisors*, J. Assoc. Comput. Mach.**18**(1971), 478–504. MR**307450**, https://doi.org/10.1145/321662.321664**[6]**Paul F. Camion,*Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomials*, IEEE Trans. Inform. Theory**29**(1983), no. 3, 378–385. MR**712404**, https://doi.org/10.1109/TIT.1983.1056666**[7]**David G. Cantor and Hans Zassenhaus,*A new algorithm for factoring polynomials over finite fields*, Math. Comp.**36**(1981), no. 154, 587–592. MR**606517**, https://doi.org/10.1090/S0025-5718-1981-0606517-5**[8]**A. L. Chistov,*Calculation of the Galois group over a function field of characteristic zero with an algebraically closed constant field in polynomial time*, Mathematical methods for constructing and analyzing algorithms (Russian), “Nauka” Leningrad. Otdel., Leningrad, 1990, pp. 200–232, 237 (Russian). MR**1082380****[9]**J. H. Davenport & B. M. Trager,*Factorization Over Finitely Generated Fields*, Proc. 1981 ACM Sympos. Symbolic and Algebraic Computation (P. Wang, ed.) 1981, pp. 200-205.**[10]**Joachim von zur Gathen,*Hensel and Newton methods in valuation rings*, Math. Comp.**42**(1984), no. 166, 637–661. MR**736459**, https://doi.org/10.1090/S0025-5718-1984-0736459-9**[11]**Joachim von zur Gathen,*Parallel algorithms for algebraic problems*, SIAM J. Comput.**13**(1984), no. 4, 802–824. MR**764180**, https://doi.org/10.1137/0213050**[12]**Joachim von zur Gathen,*Computations in rings with valuations*, Foundations of software technology and theoretical computer science (Bangalore, 1983) Tata Inst. Fund. Res., Bombay, 1983, pp. 111–128. MR**743103****[13]**G. H. Hardy & E. M. Wright,*An Introduction to the Theory of Numbers*, Clarendon Press, Oxford, 1962.**[14]**Erich Kaltofen,*A polynomial-time reduction from bivariate to univariate integral polynomial factorization*, 23rd annual symposium on foundations of computer science (Chicago, Ill., 1982) IEEE, New York, 1982, pp. 57–64. MR**780381****[15]**Erich Kaltofen,*Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization*, SIAM J. Comput.**14**(1985), no. 2, 469–489. MR**784750**, https://doi.org/10.1137/0214035**[16]**Donald E. Knuth,*The art of computer programming. Vol. 2*, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR**633878****[17]**A. Lempel, G. Seroussi, and S. Winograd,*On the complexity of multiplication in finite fields*, Theoret. Comput. Sci.**22**(1983), no. 3, 285–296. MR**693061**, https://doi.org/10.1016/0304-3975(83)90108-1**[18]**A. K. Lenstra,*Factoring Multivariate Polynomials Over Finite Fields*, Proc. 15th ACM Sympos. Theory of Computing, 1983, pp. 189-192.**[19]**A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász,*Factoring polynomials with rational coefficients*, Math. Ann.**261**(1982), no. 4, 515–534. MR**682664**, https://doi.org/10.1007/BF01457454**[20]**D. R. Musser,*Algorithms for Polynomial Factorization*, Ph.D. thesis and TR 134, Univ. of Wisconsin, 1971.**[21]**Michael O. Rabin,*Probabilistic algorithms in finite fields*, SIAM J. Comput.**9**(1980), no. 2, 273–280. MR**568814**, https://doi.org/10.1137/0209024**[22]**T. Schönemann, "Grundzüge einer allgemeinen Theorie der höheren Congruenzen, deren Modul eine reelle Primzahl ist,"*J. Reine Angew. Math.*, v. 31, 1846, pp. 269-325.**[23]**A. Schönhage, "Schnelle Multiplication von Polynomen über Körpern der Characteristic 2,"*Acta Inform.*, v. 7, 1977, pp. 395-398.**[24]**A. Schönhage and V. Strassen,*Schnelle Multiplikation grosser Zahlen*, Computing (Arch. Elektron. Rechnen)**7**(1971), 281–292 (German, with English summary). MR**292344**, https://doi.org/10.1007/bf02242355**[25]**B. L. van der Waerden,*Modern Algebra*, Vol. 1, Ungar, New York, 1953.**[26]**Hermann Weyl,*Algebraic Theory of Numbers*, Annals of Mathematics Studies, no. 1, Princeton University Press, Princeton, N. J., 1940. MR**0002354**

Retrieve articles in *Mathematics of Computation*
with MSC:
12E05,
11Y16,
68Q40

Retrieve articles in all journals with MSC: 12E05, 11Y16, 68Q40

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1985-0790658-X

Keywords:
Polynomial factorization,
multivariate polynomials,
finite fields,
probabilistic algorithms

Article copyright:
© Copyright 1985
American Mathematical Society