Computing automorphisms of abelian number fields

Abstract:

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$.