
University of Bonn > Department of Computer Science > Chair V  
CSReports 2008  Copyright 2008 University of Bonn, Department of Computer Science, 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
Deutsch 
University of Bonn > Department of Computer Science > Chair V 