Algorithmic enumeration of ideal classes for quaternion orders (Q6828964)

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.