Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Remote Access
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)


Factorization of multivariate polynomials over finite fields

Authors: J. von zur Gathen and E. Kaltofen
Journal: Math. Comp. 45 (1985), 251-261
MSC: Primary 12E05; Secondary 11Y16, 68Q40
MathSciNet review: 790658
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 12E05, 11Y16, 68Q40

Retrieve articles in all journals with MSC: 12E05, 11Y16, 68Q40

Additional Information

PII: S 0025-5718(1985)0790658-X
Keywords: Polynomial factorization, multivariate polynomials, finite fields, probabilistic algorithms
Article copyright: © Copyright 1985 American Mathematical Society

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia