A Polynomial Time Nilpotence Test for Galois Groups and Related Results
<|reference_start|>A Polynomial Time Nilpotence Test for Galois Groups and Related Results: We give a deterministic polynomial-time algorithm to check whether the Galois group $\Gal{f}$ of an input polynomial $f(X) \in \Q[X]$ is nilpotent: the running time is polynomial in $\size{f}$. Also, we generalize the Landau-Miller solvability test to an algorithm that tests if $\Gal{f}$ is in $\Gamma_d$: this algorithm runs in time polynomial in $\size{f}$ and $n^d$ and, moreover, if $\Gal{f}\in\Gamma_d$ it computes all the prime factors of $# \Gal{f}$.<|reference_end|>
@article{arvind2006a,
    title={A Polynomial Time Nilpotence Test for Galois Groups and Related Results},
    author={V. Arvind and Piyush P Kurur},
    journal={arXiv preprint arXiv:cs/0605050},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0605050},
    primaryClass={cs.CC cs.DS}
}