Fast recognition of alternating and symmetric Galois groups

If a polynomial over Q is written down "at random", then its Galois group will, with probability 1, be S-n or A(n) (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 S-n or A(n)" or "the Galois group is likely to be smaller". The method involves reducing the polynomial module primes, using the Chebotarev Density Theorem and the properties of permutation groups. (C) 2000 Elsevier Science B.V. All rights reserved. MSG: 20P05; 12Y05.