Algorithmic enumeration of ideal classes for quaternion orders
This paper deals with the counting and enumeration of the (right) ideal classes of an Eichler order in a quaternion algebra defined over a number field. More precisely, the following problems are studied:\N\NPROBLEM (ClassUnitGroup(\({\mathbb Z}_F\))). \textit{Given the ring of integers \({\mathbb Z}_F\) of a number field \(F\), compute the class group \(\text{Cl}{\mathbb Z}_F\) and unit group} \({\mathbb Z}_F^*\)\N\NPROBLEM (ClassNumber(\(\mathcal{O}\))). \textit{Given an Eichler order \(\mathcal{O}\) in a quartenion algebra over a number field \(F\), compute the class number} \(h(\mathcal{O})\).\N\NPROBLEM (ClassSet(\(\mathcal{O}\))). \textit{Given an Eichler order \(\mathcal{O}\) in a quartenion algebra over a number field \(F\), compute a set of representatives for the set of invertible right \(\mathcal{O}\)-ideal classes} {Cl}\(\mathcal{O}\).\N\NThe authors prove that if the Eichler order \(\mathcal{O}\) is indefinite, Problem ClassNumber(\(\mathcal{O}\)) is deterministic polynomial time reducible to Problem ClassUnitGroup (\({\mathbb Z}_F\)). Furthermore, it is shown that if \(\mathcal{O}\) is definite, then Problem ClassNumber(\(\mathcal{O}\)) is reducible in probabilistic polynomial time \N\[\NO(d_F^{3/2} \log^4d_F +\log^2N D) \N\]\N to the factorization of the discriminant \(D\) of \(\mathcal{O}\) and \(O(2^n)\) instances of Problem (ClassUnitGroup) with fields having discriminant of size \(O(d_F^{5/2})\) (where \(n\) and \(d_F\) is the degree and the absolute discriminant of \(F\), respectively). As consequence of these result follows that there is a probabilistic polynomial time algorithm to solve Problem (ClassUnitGroup) over a fixed field \(F\) for indefinite orders and definite orders with factored discriminants. Finally, it is proved that there exists an algorithm to solve Problem (ClassSet) for orders over a fixed field \(F\) which runs in probabilistic polynomial time in the size of the output for indefinite orders and for definite orders with factored discriminant.
- Simple power analysis attack on SQIsign
- Generalizing Hurwitz's quaternionic proof of Lagrange's and Jacobi's four-square theorems
- A reduction from Hawk to the principal ideal problem in a quaternion algebra
- SQIsign2D-West. The fast, the small, and the safer
- SQIsign2D-East: a new signature scheme using 2-dimensional isogenies
- \textsf{Qlapoti}: simple and efficient translation of quaternion ideals to isogenies
- Unconditional foundations for supersingular isogeny-based cryptography
- Better bounds for finding fixed-degree isogenies via Coppersmith's method
- Determination of the stably free cancellation property for orders
This page was built for publication: Algorithmic enumeration of ideal classes for quaternion orders
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6828964)
