A Polynomial Time Nilpotence Test for Galois Groups and Related Results

Details A Polynomial Time Nilpotence Test for Galois Groups and Related Results A Polynomial Time Nilpotence Test for Galois Groups and Related Results

2006-05-11

arxiv.org/abs/cs/0605050v1

Computer Science

Computational Complexity

12 pages

Scientific paper

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}$.

Affiliated with

Also associated with

No associations

Rating

A Polynomial Time Nilpotence Test for Galois Groups and Related Results does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Polynomial Time Nilpotence Test for Galois Groups and Related Results, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Polynomial Time Nilpotence Test for Galois Groups and Related Results will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-469490