TR08-099 Authors: Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena

Publication: 19th November 2008 15:52

Downloads: 3188

Keywords:

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

theory

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.