|
Zapiski Nauchnykh Seminarov LOMI, 1989, Volume 176, Pages 104–117
(Mi znsl4535)
|
|
|
|
This article is cited in 5 scientific papers (total in 5 papers)
Factoring a solvable polynomial over a finite field and Generalized Riemann Hypothesis
S. A. Evdokimov
Abstract:
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).
Citation:
S. A. Evdokimov, “Factoring a solvable polynomial over a finite field and Generalized Riemann Hypothesis”, Computational complexity theory. Part 4, Zap. Nauchn. Sem. LOMI, 176, "Nauka", Leningrad. Otdel., Leningrad, 1989, 104–117; J. Soviet Math., 59:3 (1992), 842–849
Linking options:
https://www.mathnet.ru/eng/znsl4535 https://www.mathnet.ru/eng/znsl/v176/p104
|
Statistics & downloads: |
Abstract page: | 339 | Full-text PDF : | 146 |
|