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 α.
68
227
1179-1186
1179-1186
American Mathematical Society (AMS)