Computing automorphisms of abelian number fields

Let $L=\mathbb{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 $\operatorname{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$.