Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2008 Copyright 2008 Universität Bonn, Institut für Informatik, Abt. V
85295

20.11.2008

Trading GRH for Algebra: Algorithms for Factoring Polynomials
and Related Structures

Gábor Ivanyos, Marek Karpinski, Lajos Rónyai and Nitin Saxena
[Download PostScript] [Download PDF]

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(nlog 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 A of dimension n over a finite field k. There is a deterministic poly(nlog n, log |k|) time algorithm to find a zero divisor in A. This is the best known deterministic GRH-free result since Rónyai (1990) first studied the problem of finding zero divisors in finite algebras and showed that this problem has the same complexity as factoring polynomials over finite fields.
  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. This is the best known deterministic GRH-free result since Evdokimov (1989) showed that cyclotomic polynomials can be factored over finite fields in deterministic polynomial time assuming GRH.
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, Teichmüller subgroups, to the case of commutative semisimple algebras with automorphisms. These generalized constructs help eliminate the dependence on GRH.
Last Change: 11/20/08 at 15:25:50
 English
Universität Bonn -> Institut für Informatik -> Abteilung V