Fast recognition of alternating and symmetric Galois groups

If a polynomial over is written down “at random”, then its Galois group will, with probability 1, be Sn or An (see also Heintz (Theoret. Comput. Sci. 47(1986) 99–105)). However, if the polynomial arises through some mathematical operations, it is likely to have a much smaller Galois group. In this paper, we present probabilistic tests which will, for any polynomial, return either the answer “the Galois group is definitely one of Sn or An” or “the Galois group is likely to be smaller”. The method involves reducing the polynomial modulo primes, using the Chebotarev Density Theorem and the properties of permutation groups.