Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


Factoring multivariate polynomials over large finite fields
HTML articles powered by AMS MathViewer

by Da Qing Wan PDF
Math. Comp. 54 (1990), 755-770 Request permission


A simple probabilistic algorithm is presented to find the irreducible factors of a bivariate polynomial over a large finite field. For a polynomial $f(x,y)$ over ${F_q}$ of total degree n, our algorithm takes at most \[ {n^{4.89}}{\log ^2}n\log q\] operations in ${F_q}$ to factor $f(x,y)$ completely. This improves a probabilistic factorization algorithm of von zur Gathen and Kaltofen, which takes \[ O({n^{11}}\log n\log q)\] operations to factor $f(x,y)$ completely over ${F_q}$. The algorithm can be easily generalized to factor multivariate polynomials over finite fields. We shall give two further applications of the idea involved in the algorithm. One is concerned with exponential sums; the other is related to permutational polynomials over finite fields (a conjecture of Chowla and Zassenhaus).
Similar Articles
Additional Information
  • © Copyright 1990 American Mathematical Society
  • Journal: Math. Comp. 54 (1990), 755-770
  • MSC: Primary 11T06; Secondary 12-04, 68Q40
  • DOI:
  • MathSciNet review: 1011448