A Terr algorithm for computations in the infrastructure of real-quadratic number fields
The authors apply a variant of the baby-step giant-step algorithm given by \textit{D. C. Terr} [Math. Comput. 69, No. 230, 767--773 (2000; Zbl 0940.68038)] for determining the infrastructure of an order \({\mathcal O}\) of a quadratic number field. They obtain algorithms for calculating the fundamental unit and for deciding the equivalence of \({\mathcal O}\)-ideals. If \(\Delta\) and \(R\) denote the discriminant and the regulator of the order those algorithms require time and space \(O((\log \Delta+\sqrt{R})(\log \Delta)^2)\). This is smaller than that of all previously designed unconditional deterministic methods for these tasks. An application to the calculation of the class group (of invertible ideals) and to the discrete logarithm problem in this group is also discussed.
- A modification of Shanks' baby-step giant-step algorithm
- Binary quadratic forms. An algorithmic approach
- Computing Arakelov class groups
- Computing the structure of a finite abelian group
- Explicit Bounds for Primality Testing and Related Problems
- scientific article; zbMATH DE number 3765915 (Why is no real title available?)
- scientific article; zbMATH DE number 1516550 (Why is no real title available?)
- scientific article; zbMATH DE number 3353398 (Why is no real title available?)
- On some computational problems in finite abelian groups
- On the Infrastructure of the Principal Ideal Class of an Algebraic Number Field of Unit Rank One
This page was built for publication: A Terr algorithm for computations in the infrastructure of real-quadratic number fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2642773)
