Abstract | ||
---|---|---|
We give the first polynomial-time algorithm for checking whether the Galois group Gal(f) of an input polynomial f(X) ∈ Q[X] is nilpotent: the running time of our algorithm is bounded by a polynomial in the size of the coefficients of f and the degree of f. Additionally, we give a deterministic polynomial-time algorithm that, when given as input a polynomial f(X) ∈ Q[X] with nilpotent Galois group, computes for each prime factor p of # Gal(f), a polynomial gp(X)∈ Q[X] whose Galois group of is the p-Sylow subgroup of Gal(f). |
Year | DOI | Venue |
---|---|---|
2012 | 10.1145/2229163.2229176 | ACM Transactions on Algorithms |
Keywords | Field | DocType |
polynomial gp,galois group,prime factor p,deterministic polynomial-time algorithm,testing nilpotence,nilpotent galois group,polynomial time,input polynomial,p-sylow subgroup,polynomial-time algorithm | Discrete mathematics,Combinatorics,Minimal polynomial (field theory),Resolvent,Separable polynomial,Galois cohomology,Minimal polynomial (linear algebra),Galois extension,Generic polynomial,Galois group,Mathematics | Journal |
Volume | Issue | ISSN |
8 | 3 | 1549-6325 |
Citations | PageRank | References |
1 | 0.44 | 10 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
V. Arvind | 1 | 122 | 12.03 |
Piyush P. Kurur | 2 | 88 | 9.41 |