Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR08-099 | 19th November 2008 00:00

Trading GRH for algebra: algorithms for factoring polynomials and related structures


Authors: Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena
Publication: 19th November 2008 15:52
Downloads: 1460


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 subexponential
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 GRH-free results, most striking of which are:

(1) Given a noncommutative algebra over a finite field, there is a deterministic subexponential time algorithm to find
a zero divisor.

(2) Given a positive integer r>4 such that either 4|r or
r has two distinct prime factors. There is a deterministic polynomial time
algorithm to find a nontrivial factor of the r-th cyclotomic
polynomial over a finite field.

In this paper, following the seminal work of Lenstra (1991)
on constructing isomorphisms between finite fields,
we further generalize classical Galois
constructs like cyclotomic extensions, Kummer extensions,
Teichmuller subgroups, to the case of commutative
semisimple algebras with automorphisms. These
generalized constructs help eliminate the dependence on GRH.

ISSN 1433-8092 | Imprint