Computing Automorphisms of Abelian Number Fields

Let L = ℚ(α) be an abelian number field of degree n. Most algorithms for computing the lattice of subfields of L require the computation of all the conjugates of α. This is usually achieved by factoring the minimal polynomial mα(x) of α over L. In practice, the existing algorithms for factoring polynomials over algebraic number fields can handle only problems of moderate size. In this paper we describe a fast probabilistic algorithm for computing the conjugates of α, which is based on p-adic techniques. Given mα(x) and a rational prime p which does not divide the discriminant disc(mα(x)) of mα(x), the algorithm computes the Frobenius automorphism of p in time polynomial in the size of p and in the size of mα(x). By repeatedly applying the algorithm to randomly chosen primes it is possible to compute all the conjugates of α.