
University of Bonn > Department of Computer Science > Chair V  
CSReports 2008  Copyright 2008 University of Bonn, Department of Computer Science, Abt. V  
85289 14.04.2008 
Schemes for Deterministic Polynomial Factoring
Gábor Ivanyos, Marek Karpinski and Nitin Saxena [Download PostScript] [Download PDF] In this work we relate the deterministic complexity of factoring polynomials (over finite fields) to certain combinatorial objects we call mschemes. We extend the known conditional deterministic subexponential time polynomial factoring algorithm for finite fields to get an underlying mscheme. We demonstrate how the properties of mschemes relate to improvements in the deterministic complexity of factoring polynomials over finite fields assuming the generalized Riemann Hypothesis (GRH). In particular, we give the first deterministic polynomial time algorithm (assuming GRH) to find a nontrivial factor of a polynomial of prime degree n where (n1) is a smooth number. 

Last Change:
04/14/08 at 14:00:04
Deutsch 
University of Bonn > Department of Computer Science > Chair V 