TR08-043 Authors: Gábor Ivanyos, Marek Karpinski, Nitin Saxena

Publication: 15th April 2008 09:53

Downloads: 3484

Keywords:

In this work we relate the deterministic

complexity of factoring polynomials (over

finite

fields) to certain combinatorial objects we

call

m-schemes. We extend the known conditional

deterministic subexponential time polynomial

factoring algorithm for finite fields to get an

underlying m-scheme. We demonstrate how the

properties of m-schemes 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 (n-1) is a smooth number.