
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 2012  Copyright 2012 Universität Bonn, Institut für Informatik, Abt. V  
85329 25.05.2012 
Deterministic Polynomial Factoring and Association Schemes
Manuel Arora, Gábor Ivanyos, Marek Karpinski and Nitin Saxena [Download PostScript] [Download PDF]
The problem of finding a nontrivial factor of a polynomial f(x) over a finite field F_{q} has many known efficient, but randomized, algorithms. The deterministic complexity of this problem is a famous open question even assuming the generalized Riemann hypothesis (GRH). In this work we improve the state of the art by focusing on prime degree polynomials; let n be the degree. If (n1) has a 'large' rsmooth divisor s, then we find a nontrivial factor of f(x) in deterministic poly(n^{r},log q) time; assuming GRH and that s=Ω(√n/2^{r}). Thus, for r=O(1) our algorithm is polynomial time. Further, for r=Ω(log log n) there are infinitely many prime degrees n for which our algorithm is applicable and better than the best known; assuming GRH. 

Last Change:
05/25/12 at 13:36:31
English 
Universität Bonn > Institut für Informatik > Abteilung V 