Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 

 

Trading GRH for algebra: Algorithms for factoring polynomials and related structures


Authors: Gábor Ivanyos, Marek Karpinski, Lajos Rónyai and Nitin Saxena
Journal: Math. Comp. 81 (2012), 493-531
MSC (2010): Primary 68W30, 12Y05, 16Z05
DOI: https://doi.org/10.1090/S0025-5718-2011-02505-6
Published electronically: May 10, 2011
MathSciNet review: 2833506
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we develop a general technique to eliminate the assumption of the Generalized Riemann Hypothesis (GRH) from various deterministic polynomial factoring algorithms over finite fields. It is the first bona fide progress on that issue for more than 25 years of study of the problem. Our main results are basically of the following form: either we construct a nontrivial factor of a given polynomial or compute a nontrivial automorphism of the factor algebra of the given polynomial. Probably the most notable application of such automorphisms is efficiently finding zero divisors in noncommutative algebras. The proof methods used in this paper exploit virtual roots of unity and lead to efficient actual polynomial factoring algorithms in special cases.


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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 68W30, 12Y05, 16Z05

Retrieve articles in all journals with MSC (2010): 68W30, 12Y05, 16Z05


Additional Information

Gábor Ivanyos
Affiliation: Computer and Automation Research Institute of the Hungarian Academy of Sciences, Lágymányosi u. 11, 1111 Budapest, Hungary.
Email: Gabor.Ivanyos@sztaki.hu

Marek Karpinski
Affiliation: Department of Computer Science and Hausdorff Center for Mathematics, University of Bonn, 53117 Bonn, Germany
Email: marek@cs.uni-bonn.de

Lajos Rónyai
Affiliation: Computer and Automation Research Institute of the Hungarian Academy of Sciences, Lágymányosi u. 11, 1111 Budapest, Hungary and Department of Algebra, Budapest University of Technology and Economics, Műegyetem rkp. 3-9, 1111 Budapest, Hungary.
Email: lajos@ilab.sztaki.hu

Nitin Saxena
Affiliation: Hausdorff Center for Mathematics, University of Bonn, 53115 Bonn, Germany
Email: ns@hcm.uni-bonn.de

DOI: https://doi.org/10.1090/S0025-5718-2011-02505-6
Received by editor(s): September 12, 2009
Received by editor(s) in revised form: November 10, 2010
Published electronically: May 10, 2011
Article copyright: © Copyright 2011 American Mathematical Society