Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR08-043 | 12th April 2008 00:00

Schemes for Deterministic Polynomial Factoring

RSS-Feed




TR08-043
Authors: Gábor Ivanyos, Marek Karpinski, Nitin Saxena
Publication: 15th April 2008 09:53
Downloads: 1649
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint