Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

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.

 

Trading GRH for algebra: Algorithms for factoring polynomials and related structures
HTML articles powered by AMS MathViewer

by Gábor Ivanyos, Marek Karpinski, Lajos Rónyai and Nitin Saxena PDF
Math. Comp. 81 (2012), 493-531 Request permission

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
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
  • Received by editor(s): September 12, 2009
  • Received by editor(s) in revised form: November 10, 2010
  • Published electronically: May 10, 2011
  • © Copyright 2011 American Mathematical Society
  • Journal: Math. Comp. 81 (2012), 493-531
  • MSC (2010): Primary 68W30, 12Y05, 16Z05
  • DOI: https://doi.org/10.1090/S0025-5718-2011-02505-6
  • MathSciNet review: 2833506