Factoring a solvable polynomial over a finite field and Generalized Riemann Hypothesis

S. A. Evdokimov

Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part 4, Tome 176 (1989), pp. 104-117

Résumé

Let $p$ be a prime and $f\in\mathbb{Z}[X]$ be a polynomial with leading coefficient relatively prime to $p$ and with solvable Galois group over $\mathbb{Q}$. According to [2] , the solvability of $f$ can be checked in time polynomial in $L(f)$, where $L(f)$ is the size of $f$. Assuming the Generalized Riemann Hypothesis (GRH) we construct a deterministic algorithm for decomposing $f\mod p$ into irreducible factors over the field $\mathbb{F}_{p^m}$ with $p^m$ elements. Its running time is polynomial in $\log p$, $m$ and $L(f)$. This result generalizes the main result of [1] , where only polynomials $f$ with abelian Galois group have been considered. As it follows from our algorithm, in the case of an irreducible solvable $f$ one can find a natural number $s$ such that $s$ is polynomial in $\mathrm{deg}\,f$ and $f\mod p$ is completely decomposed into linear factors over $\mathbb{F}_{p^s}$. Note that in this case the order of Galois group of $f$ can be exponential in $\mathrm{deg}\,f$. Besides the following three problems, formulated in [1] and being of interest by themselves, are solved within time polynomial in $\log p$, $m$, $n$ (under GRH): 1) constructing the finite field $\mathbb{F}_{p^m}$, 2) constructing all isomorphisms between two realizations of $\mathbb{F}_{p^m}$, 3) extracting $n$-th roots in $\mathbb{F}_{p^m}$. The results of the paper were presented at the Eighth All Union Conference on Mathematical Logic (Moscow, 1986, see [12]) and at the Seventh Hungarian Colloquium on Combinatorics (Eger, 1987).