Let L = Q(#alpha#) 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 #alpha#. This is usually achieved by factoring the minimal polynomial m_#alpha#(x) of #alpha# 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 #alpha#, which is based on p-adic techniques. Given m_#alpha#(x) and a rational prime p which does not divide the discriminant disc(m_#alpha#(x)) of m_#alpha#(x), the algorithm computes the Frobenius automorphism of p in time polynomial in the size of p and in the size of m_#alpha#(x). By repeatedly applying the algorithm to randomly chosen primes it is possible to compute all the conjugates of #alpha#.
展开▼
