Computing discrete logarithms in quadratic orders (Q1590363): Difference between revisions

Let \(\Delta \equiv 0,1 \pmod{4}\) be a nonsquare integer. The quadratic order of discriminant \(\Delta\) is defined as the \(\mathbb{Z}\)-module \[ \mathcal{O}_{\Delta} = \mathbb{Z} + {\Delta + \sqrt{\Delta} \over 2}{\mathbb{Z}} . \] The field of quotients is \(\mathbb{Q}({\sqrt{\Delta}})\). The discrete logarithm problem (DLP) in \(\mathcal{O}_{\Delta}\) is: given two ideals \({\mathfrak a},{\mathfrak b} \in \mathcal{O}_{\Delta}\), compute \(\alpha \in \mathbb{Q}({\sqrt{\Delta}})\) and \(x \in \mathbb{Z}_{\geq 0}\) such that \[ {\mathfrak a} = \alpha {\mathfrak b}^x \] or determine that no such \(x\) and \(\alpha\) exists. It is observed that in imaginary quadratic orders the most difficult part is to compute the exponent \(x\) while in real quadratic orders, in general, the most difficult part is to find \(\alpha\) where one has to do principal ideal testing. This work presents efficient algorithms for computing the DLP in the class group of a quadratic order based on the work of Düllman and Abel. It is shown how the idea of sieving can be applied to improve the performance of these algorithms. Computational results are presented which show that these techniques yield a significant increase in the size of the discriminants for which these discrete logarithm problems can be solved.