We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A proof of the conjectured run time of the Hafner-McCurley class group algorithm.
- Authors
Biasse, Jean-François; Erukulangara, Muhammed Rashad
- Abstract
We present a proof under a generalization of the Riemann Hypothesis that the class group algorithm of Hafner and McCurley runs in expected time $ e^{\left(3/\sqrt{8}+o(1)\right)\sqrt{\log d\log\log d}} $ where $ -d $ is the discriminant of the input imaginary quadratic order. In the original paper, an expected run time of $ e^{\left(\sqrt{2}+o(1)\right)\sqrt{\log d\log\log d}} $ was proven, and better bounds were conjectured. To achieve a proven result, we rely on a mild modification of the original algorithm, and on recent results on the properties of the Cayley graph of the ideal class group.
- Subjects
RIEMANN hypothesis; CAYLEY graphs; ALGORITHMS; QUADRATIC fields
- Publication
Advances in Mathematics of Communications, 2023, Vol 17, Issue 6, p1
- ISSN
1930-5346
- Publication type
Article
- DOI
10.3934/amc.2021055