Testing nilpotence of galois groups in polynomial time
V. Arvind, Piyush P. Kurur · ACM Transactions on Algorithms · 2012
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 g p ( X )∈ Q[ X ] whose Galois group of is the p -Sylow subgroup of Gal( f ).