Reducing ideal arithmetic to linear algebra problems
Most (implemented) algorithms in number theory rely on ideal arithmetic that is usually reduced to computations in free \(\mathbb{Z}\)-modules \(\Lambda\). In this context usually one knows a common multiplier \(m\) for the modules involved, i.e. \(m\mathbb{Z}^n\subset \Lambda \subset \mathbb{Z}^n\). Using this fact one can reduce the linear algebra in \(\mathbb{Z}\) to linear algebra in \(\mathbb{Z}/m\mathbb{Z}\). Extending ideas contained in [\textit{J. A. Howell}, Linear Multilinear Algebra 19, 67-77 (1986; Zbl 0596.15013)], the author gives procedures for determining the span and null space of matrices defined over \(\mathbb{Z}/m\mathbb{Z}\). The key ingredient is an extended gcd algorithm that is used to replace the inversions (that may fail) of the usual Gaussian elimination. As an application he gives explicit algorithms for ideal arithmetic in (the maximal) orders of extensions of \(\mathbb{Q}\), namely for the computation of the sum, intersection, product and quotient of ideals, whenever the operation is defined. For the entire collection see [Zbl 0891.00022].
This page was built for publication: Reducing ideal arithmetic to linear algebra problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3840172)
