Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Factoring multivariate polynomials over large finite fields

Author: Da Qing Wan
Journal: Math. Comp. 54 (1990), 755-770
MSC: Primary 11T06; Secondary 12-04, 68Q40
MathSciNet review: 1011448
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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

$\displaystyle {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

$\displaystyle 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).

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11T06, 12-04, 68Q40

Retrieve articles in all journals with MSC: 11T06, 12-04, 68Q40

Additional Information

Article copyright: © Copyright 1990 American Mathematical Society