Name
Abstract | ||
|---|---|---|
Assuming the generalized Riemann hypothesis, we prove the following complexity bounds: The order of the Galois group of an arbitrary polynomial f (x) is an element of Z [x] can be computed in P-#P. Furthermore, the order can be approximated by a randomized polynomial-time algorithm with access to an NP oracle. For polynomials f with solvable Galois group we show that the order can be computed exactly by a randomized polynomial-time algorithm with access to an NP oracle. For all polynomials f with abelian Galois group we show that a generator set for the Galois group can be computed in randomized polynomial time. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1007/978-3-540-24587-2_73 | ALGORITHMS AND COMPUTATION, PROCEEDINGS |
Keywords | DocType | Volume |
galois group,galois theory,upper bound | Conference | 2906 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
2 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vikraman Arvind | 1 | 296 | 38.18 |
| Piyush P. Kurur | 2 | 88 | 9.41 |