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, Probabilistic Algorithms in Finite Fields, Proc. 22nd Sympos. Foundations Comp. Sci., IEEE, 1981, pp. 394-398.
- 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, Factorization Over Finitely Generated Fields, Proc. 1981 ACM Sympos. Symbolic and Algebraic Computation (P. Wang, ed.) 1981, pp. 200-205.
- 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, An Introduction to the Theory of Numbers, Clarendon Press, Oxford, 1962.
- 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, Factoring Multivariate Polynomials Over Finite Fields, Proc. 15th ACM Sympos. Theory of Computing, 1983, pp. 189-192.
- 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, Algorithms for Polynomial Factorization, Ph.D. thesis and TR 134, Univ. of Wisconsin, 1971.
- 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," 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.
- 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, Modern Algebra, Vol. 1, Ungar, New York, 1953.
- Hermann Weyl, Algebraic Theory of Numbers, Annals of Mathematics Studies, No. 1, Princeton University Press, Princeton, N. J., 1940. MR 0002354
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