2008/11/19 by Gábor Ivanyos, Ivanyos, Gábor, Marek Karpiński +5
Computer Science · #Coding theory and cryptography #Computational Complexity (cs.CC) #Cryptography and Data Security #Cryptography and Residue Arithmetic #FOS: Computer and information sciences #Symbolic Computation (cs.SC)
paper · pdf · doi:10.48550/arxiv.0811.3165
openalex publication_date 2008/11/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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.