Algorithms for Algebraic Number Theory

I think the best overall reference for algorithms for doing basic algebraic number theory computations is [Coh93].

Our main long-term algorithmic goals for this book (which we won't succeed at reaching) are to understand good algorithms for solving the following problems in particular cases:

• Ring of integers: Given a number field $K$ (by giving a polynomial), compute the full ring $\O _K$ of integers.
• Decomposition of primes: Given a prime number $p\in\mathbf{Z}$, find the decomposition of the ideal $p\O _K$ as a product of prime ideals of $\O _K$.
• Class group: Compute the group of equivalence classes of nonzero ideals of $\O _K$, where $I$ and $J$ are equivalent if there exists $\alpha \in \O _K$ such that $IJ^{-1}=(\alpha)$.
• Units: Compute generators for the group of units of $\O _K$.

As we will see, somewhat surprisingly it turns out that algorithmically by far the most time-consuming step in computing the ring of integers $\O _K$ seems to be to factor the discriminant of a polynomial whose root generates the field $K$. The algorithm(s) for computing $\O _K$ are quite complicated to describe, but the first step is to factor this discriminant, and it takes much longer in practice than all the other complicated steps.