Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

On bivariate polynomial factorization over finite fields


Author: Igor E. Shparlinski
Journal: Math. Comp. 60 (1993), 787-791
MSC: Primary 12E20; Secondary 68Q40
DOI: https://doi.org/10.1090/S0025-5718-1993-1176716-3
MathSciNet review: 1176716
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] E. Bach and V. Shoup, Factoring polynomials using fewer random bits, J. Symbolic Comput. 9 (1990), 229-239. MR 1056625 (91h:11149)
  • [2] M. Ben-Or, Probabilistic algorithms in finite fields, Proc. 22 IEEE Sympos. Found. Comput. Sci., 1981, pp. 394-398.
  • [3] E. R. Berlekamp, Factoring polynomials over finite fields, Bell System Tech. J. 46 (1967), 1853-1859. MR 0219231 (36:2314)
  • [4] -, Algebraic coding theory, McGraw-Hill, New York, 1968. MR 0238597 (38:6873)
  • [5] -, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713-735. MR 0276200 (43:1948)
  • [6] D. G. Cantor and H. Zassenhaus, A new algorithm for factoring polynomials over finite fields, Math. Comp. 36 (1981), 587-592. MR 606517 (82e:12020)
  • [7] A. L. Chistov and D. Yu. Grigoriev, Polynomial-time factoring of the multivariable polynomials over a global field, Preprint LOMI E-5-82, Leningrad, 1982.
  • [8] J. Von zur Gathen and E. Kaltofen, Factorization of multivariate polynomials over finite fields, Math. Comp. 45 (1985), 251-261. MR 790658 (87a:12005)
  • [9] D. Yu. Grigoriev, Factoring polynomials over a finite field and solving systems of algebraic equations, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. 137 (1984), 20-79. (Russian) MR 762096 (86g:11077a)
  • [10] J. Knopfmacher, Analytic arithmetic of algebraic function fields, Lecture Notes in Pure and Appl. Math., vol. 50, Marcel Dekker, New York, 1979. MR 545904 (81d:10031)
  • [11] A. K. Lenstra, Factoring multivariate polynomials over finite fields, J. Comput. System Sci. 30 (1985), 235-248. MR 801825 (87a:11124)
  • [12] R. Lidl and H. Niederreiter, Finite fields, Addison-Wesley, Reading, MA, 1983. MR 746963 (86c:11106)
  • [13] V. Shoup, On the deterministic complexity of factoring polynomials over finite fields, Inform. Process. Lett. 33 (1990), 261-267. MR 1049276 (91f:11088)
  • [14] -, Smoothness and factoring polynomials over finite fields, Inform. Process. Lett. 38 (1991), 39-42. MR 1103697 (92f:11178)
  • [15] -, A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic, Proc. Sympos. on Symbolic and Algebraic Comput., 1991, pp. 14-21.
  • [16] D. Q. Wan, Factoring multivariate polynomials over large finite fields, Math. Comp. 54 (1990), 755-770. MR 1011448 (90i:11141)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 12E20, 68Q40

Retrieve articles in all journals with MSC: 12E20, 68Q40


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1993-1176716-3
Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society