Dedekind factorization cycle test (source code)

= Dedekind factorization cycle test
{c}

Let $f\in\mathbb Z[X]$ be monic and separable over $\mathbb Q$. If its reduction modulo a <prime number> $p$ is squarefree, factor it into distinct irreducible polynomials of degrees $d_1,\ldots,d_r$. The <Galois group of a polynomial> then contains an element with cycle lengths $d_1,\ldots,d_r$: a <Frobenius automorphism> at a prime of the splitting field acts on the reduced roots in precisely those orbits.

The squarefree-reduction condition, equivalently $p\nmid\operatorname{disc}(f)$, ensures that reduction distinguishes the roots. Merely assuming that $p$ is unramified in the number field generated by a root is insufficient for an arbitrary generator. For example, $X^2-5$ has repeated reduction $(X+1)^2$ modulo two even though two is unramified in $\mathbb Q(\sqrt5)$; its power basis has index two. For a good prime, a quadratic times an irreducible cubic therefore gives a permutation with one 2-cycle and one 3-cycle, a useful constraint on the Galois group.