
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 2008  Copyright 2008 Universität Bonn, Institut für Informatik, Abt. V  
85295 20.11.2008 
Trading GRH for Algebra: Algorithms for Factoring Polynomials and Related Structures Gábor Ivanyos, Marek Karpinski, Lajos Rónyai and Nitin Saxena [Download PostScript] [Download PDF] In this paper we develop techniques that eliminate the need of the Generalized Riemann Hypothesis (GRH) from various (almost all) known results about deterministic polynomial factoring over finite fields. Our main result shows that given a polynomial f(x) of degree n over a finite field k, we can find in deterministic poly(n^{log n}, log k) time either a nontrivial factor of f(x) or a nontrivial automorphism of k[x]/(f(x)) of order n. This main tool leads to various new GRHfree results, most striking of which are:


Last Change:
11/20/08 at 15:25:50
English 
Universität Bonn > Institut für Informatik > Abteilung V 