On bivariate polynomial factorization over finite fields

Shparlinski, Igor E.

doi:10.1090/S0025-5718-1993-1176716-3

On bivariate polynomial factorization over finite fields
HTML articles powered by AMS MathViewer

by Igor E. Shparlinski PDF

Math. Comp. 60 (1993), 787-791 Request permission

Abstract:

This paper shows that a recently proposed approach of D. Q. Wan to bivariate factorization over finite fields, the univariate factoring algorithm of V. Shoup, and the new bound of this paper for the average number of irreducible divisors of polynomials of a given degree over a finite field can be used to design a bivariate factoring algorithm that is polynomial for "almost all" bivariate polynomials.

References

Eric Bach and Victor Shoup, Factoring polynomials using fewer random bits, J. Symbolic Comput. 9 (1990), no. 3, 229–239. MR 1056625, DOI 10.1016/S0747-7171(08)80011-9

Probabilistic algorithms in finite fields

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, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713–735. MR 276200, DOI 10.1090/S0025-5718-1970-0276200-X
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

Polynomial-time factoring of the multivariable polynomials over a global field

J. von zur Gathen and E. Kaltofen, Factorization of multivariate polynomials over finite fields, Math. Comp. 45 (1985), no. 171, 251–261. MR 790658, DOI 10.1090/S0025-5718-1985-0790658-X
D. Yu. Grigor′ev, Factoring polynomials over a finite field and solution of systems of algebraic equations, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 137 (1984), 20–79 (Russian, with English summary). Theory of the complexity of computations, II. MR 762096
John Knopfmacher, Analytic arithmetic of algebraic function fields, Lecture Notes in Pure and Applied Mathematics, vol. 50, Marcel Dekker, Inc., New York, 1979. MR 545904
A. K. Lenstra, Factoring multivariate polynomials over finite fields, J. Comput. System Sci. 30 (1985), no. 2, 235–248. MR 801825, DOI 10.1016/0022-0000(85)90016-9
Rudolf Lidl and Harald Niederreiter, Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. With a foreword by P. M. Cohn. MR 746963
Victor Shoup, On the deterministic complexity of factoring polynomials over finite fields, Inform. Process. Lett. 33 (1990), no. 5, 261–267. MR 1049276, DOI 10.1016/0020-0190(90)90195-4
Victor Shoup, Smoothness and factoring polynomials over finite fields, Inform. Process. Lett. 38 (1991), no. 1, 39–42. MR 1103697, DOI 10.1016/0020-0190(91)90212-Z

A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic

Da Qing Wan, Factoring multivariate polynomials over large finite fields, Math. Comp. 54 (1990), no. 190, 755–770. MR 1011448, DOI 10.1090/S0025-5718-1990-1011448-0