Computer Science – Computational Complexity
Scientific paper
2008-11-19
Computer Science
Computational Complexity
35 pages, preliminary version
Scientific paper
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 poly(n^{\log n},\log |k|) 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, we can find a zero divisor in deterministic subexponential time. (2) Given a positive integer r such that either 8|r or r has at least two distinct odd 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.
Ivanyos Gabor
Karpinski Marek
Rónyai Lajos
Saxena Nitin
No associations
LandOfFree
Trading GRH for algebra: algorithms for factoring polynomials and related structures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Trading GRH for algebra: algorithms for factoring polynomials and related structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Trading GRH for algebra: algorithms for factoring polynomials and related structures will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-429501