Computing discrete logarithms in quadratic orders (Q1590363)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Computing discrete logarithms in quadratic orders
scientific article

    Statements

    Computing discrete logarithms in quadratic orders (English)
    0 references
    19 February 2002
    0 references
    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.
    0 references
    discrete logarithm
    0 references
    principal ideal testing
    0 references
    quadratic order
    0 references
    class group
    0 references
    computational number theory
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references