A Terr algorithm for computations in the infrastructure of real-quadratic number fields (Q2642773)

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.