A new computational approach to ideal theory in number fields (Q385455): Difference between revisions

Let \(K\) be a number field with integer ring \({\mathbb Z}_K\). Then \(K\) can be described by specifying an irreducible monic polynomial \(f(X)\in{\mathbb Z}[X]\) such that \(K={\mathbb Q}(\theta)\) for some root \(\theta\) of \(f(X)\). In earlier work [\textit{J. Guàrdia} et al., J. Théor. Nombres Bordx. 23, No. 3, 667--696 (2011; Zbl 1266.11131)] and [Trans. Am. Math. Soc. 364, No. 1, 361--416 (2012; Zbl 1252.11091)] the authors developed a method for determining the factorization of \(p{\mathbb Z}_K\) into prime ideals in \({\mathbb Z}_K\). This computation associates to each prime ideal \(P\) lying over \(p{\mathbb Z}\) a list of data \([p;\phi_1,\dots,\phi_r;\phi_p]\), where \(\phi_j\) are certain monic polynomials with coefficients in \(\mathbb Z\) which are irreducible over the \(p\)-adic integer ring \({\mathbb Z}_p\). This data is referred to as an ``OM representation'' of \(P\). Using OM representations the authors are able to make computations involving fractional ideals of \(K\) while avoiding the computationally demanding task of computing a \({\mathbb Z}\)-basis for \({\mathbb Z}_K\). The authors first show how to compute the \(P\)-adic valuation function \(v_P:K^{\times}\rightarrow{\mathbb Z}\). This allows them to compute the prime factorization of a fractional ideal \(I\) in \(K\), and hence to compute the sum, product, and intersection of two fractional ideals. The authors then show how to determine a two-element generating set for \(I\); their methods don't tell us whether \(I\) is principal or not. They also show how to compute residue classes modulo \(P\) of elements of \({\mathbb Z}_K\). The authors have implemented their algorithms using the computer algebra package Magma. They give several examples which demonstrate the speed and effectiveness of their algorithms. Generally speaking, their algorithms are much faster than the corresponding built-in Magma functions as long as the degree \([K:{\mathbb Q}]\) is not too small.