Trading GRH for algebra: algorithms for factoring polynomials and related structures

Simple item page
dc.creatorIvanyos, Gábor
dc.creatorKarpinski, Marek
dc.creatorRónyai, Lajos
dc.creatorSaxena, Nitin
dc.date2008-11-19
dc.date2009-02-08
dc.date.accessioned2026-07-07T12:38:30Z
dc.date.available2026-07-07T12:38:30Z
dc.descriptionIn 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.
dc.description35 pages, preliminary version
dc.identifierhttps://arxiv.org/abs/0811.3165
dc.identifierhttp://arxiv.org/abs/0811.3165
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/218782
dc.subjectComputational Complexity
dc.subjectSymbolic Computation
dc.titleTrading GRH for algebra: algorithms for factoring polynomials and related structures
dc.typetext

Files

Collections

arXiv