Solvability by radicals is in polynomial time

摘要

A polynomial time algorithm is presented for the founding question of Galois theory: determining solvability by radicals of a monic irreducible polynomial over the integers. Also a polynomial time algorithm which expresses a root in radicals in terms of a straightline program is given. Polynomial time algorithms are demonstrated for computing blocks of imprimitivity of roots of the polynomial under the action of the Galois group, and for computing intersections of algebraic number fields. In all of the algorithms it is assumed that the number field is given by a primitive element which generates it over the rationals, that the polynomial in question is monic, and that its coefficients are in the integers.