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