## Factorization of multivariate polynomials over finite fields

HTML articles powered by AMS MathViewer

- by J. von zur Gathen and E. Kaltofen PDF
- Math. Comp.
**45**(1985), 251-261 Request permission

## 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.## References

- Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman,
*The design and analysis of computer algorithms*, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing. MR**0413592**
M. Ben-Or, - 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 - 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 - 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**, DOI 10.1145/321662.321664 - 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**, DOI 10.1109/TIT.1983.1056666 - 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**, DOI 10.1090/S0025-5718-1981-0606517-5 - 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**
J. H. Davenport & B. M. Trager, - Joachim von zur Gathen,
*Hensel and Newton methods in valuation rings*, Math. Comp.**42**(1984), no. 166, 637–661. MR**736459**, DOI 10.1090/S0025-5718-1984-0736459-9 - Joachim von zur Gathen,
*Parallel algorithms for algebraic problems*, SIAM J. Comput.**13**(1984), no. 4, 802–824. MR**764180**, DOI 10.1137/0213050 - 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**
G. H. Hardy & E. M. Wright, - 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** - 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**, DOI 10.1137/0214035 - Donald E. Knuth,
*The art of computer programming. Vol. 2*, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR**633878** - 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**, DOI 10.1016/0304-3975(83)90108-1
A. K. Lenstra, - 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**, DOI 10.1007/BF01457454
D. R. Musser, - Michael O. Rabin,
*Probabilistic algorithms in finite fields*, SIAM J. Comput.**9**(1980), no. 2, 273–280. MR**568814**, DOI 10.1137/0209024
T. Schönemann, "Grundzüge einer allgemeinen Theorie der höheren Congruenzen, deren Modul eine reelle Primzahl ist," - A. Schönhage and V. Strassen,
*Schnelle Multiplikation grosser Zahlen*, Computing (Arch. Elektron. Rechnen)**7**(1971), 281–292 (German, with English summary). MR**292344**, DOI 10.1007/bf02242355
B. L. van der Waerden, - Hermann Weyl,
*Algebraic Theory of Numbers*, Annals of Mathematics Studies, No. 1, Princeton University Press, Princeton, N. J., 1940. MR**0002354**

*Probabilistic Algorithms in Finite Fields*, Proc. 22nd Sympos. Foundations Comp. Sci., IEEE, 1981, pp. 394-398.

*Factorization Over Finitely Generated Fields*, Proc. 1981 ACM Sympos. Symbolic and Algebraic Computation (P. Wang, ed.) 1981, pp. 200-205.

*An Introduction to the Theory of Numbers*, Clarendon Press, Oxford, 1962.

*Factoring Multivariate Polynomials Over Finite Fields*, Proc. 15th ACM Sympos. Theory of Computing, 1983, pp. 189-192.

*Algorithms for Polynomial Factorization*, Ph.D. thesis and TR 134, Univ. of Wisconsin, 1971.

*J. Reine Angew. Math.*, v. 31, 1846, pp. 269-325. A. Schönhage, "Schnelle Multiplication von Polynomen über Körpern der Characteristic 2,"

*Acta Inform.*, v. 7, 1977, pp. 395-398.

*Modern Algebra*, Vol. 1, Ungar, New York, 1953.

## Additional Information

- © Copyright 1985 American Mathematical Society
- 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