ECCC-Report TR08-099https://eccc.weizmann.ac.il/report/2008/099Comments and Revisions published for TR08-099en-usWed, 19 Nov 2008 15:52:57 +0200
Paper TR08-099
| Trading GRH for algebra: algorithms for factoring polynomials and related structures |
Gábor Ivanyos,
Marek Karpinski,
Lajos Rónyai,
Nitin Saxena
https://eccc.weizmann.ac.il/report/2008/099In 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.
Wed, 19 Nov 2008 15:52:57 +0200https://eccc.weizmann.ac.il/report/2008/099