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)


On a new factorization algorithm for polynomials over finite fields

Authors: Harald Niederreiter and Rainer Göttfert
Journal: Math. Comp. 64 (1995), 347-353
MSC: Primary 11T06; Secondary 11Y16
MathSciNet review: 1265019
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A new deterministic factorization algorithm for polynomials over finite fields was recently developed by the first author. The bottleneck in this algorithm is the last stage in which the irreducible factors of the polynomial are derived from the solutions of a system of linear equations. An efficient approach to the last stage was designed by the second author for the case of finite fields of characteristic 2. In this paper, we describe a different approach to the last stage which works for arbitrary fields of positive characteristic. In particular, we obtain in this way an acceleration of the factorization algorithm of the first author which makes this algorithm polynomial time for fixed characteristic.

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

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11T06, 11Y16

Retrieve articles in all journals with MSC: 11T06, 11Y16

Additional Information

PII: S 0025-5718(1995)1265019-6
Keywords: Polynomial factorization, finite fields, arithmetic complexity
Article copyright: © Copyright 1995 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