On determining the solvability of polynomials
K. Yokoyama, Masayuki Noro, Taku Takeshima · 1990
Landau and Miller presented a method for determining the solvability of a monic irreducible polynomial over integers in polynomial time. In their method, a series of polynomials is constructed so that the original problem is reduced to determining the solvability of new polynomials. Here, we present an improved method for finding such a series of polynomials efficiently. More precisely, we introduce a new notion on a series of blocks in the set of all roots of the original polynomial under the action of its Galois group, and then present an efficient method for finding such a series of blocks by modifying Landau and Miller's method for finding minimal imprimitive blocks.