Article Contents
Article Contents
Early Access

Early Access articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Early Access publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Early Access articles via the “Early Access” tab for the selected journal.

A proof of the conjectured run time of the Hafner-McCurley class group algorithm

• * Corresponding author: Jean-François Biasse
The first author is supported by NSF grant 1846166
• 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.

Mathematics Subject Classification: Primary: 11Y16, 20C05, 11R32; Secondary: 11R29, 11R04, 11Y40, 11R18, 11R27.

 Citation:

•  [1] E. Bach, Explicit bounds for primality testing and related problems, Math. Comp., 55 (1990), 355-380.  doi: 10.1090/S0025-5718-1990-1023756-8. [2] J. Bauch, D. Bernstein, H. de Valence, T. Lange and C. van Vredendaal, Short generators without quantum computers: The case of multiquadratics, in Proceedings of EUROCRYPT 2017, 10210 (2017), 27–59. doi: 10.1007/978-3-319-56620-7_2. [3] K. Belabas, T. Kleinjung, A. Sanso and B. Wesolowski, A note on the low order assumption in class group of an imaginary quadratic number fields, Cryptology ePrint Archive, Report 2020/1310, 2020, https://eprint.iacr.org/2020/1310. [4] D. Bernstein, How to find smooth parts of integers. [5] W. Beullens, T. Kleinjung and F. Vercauteren, Csi-fish: Efficient isogeny based signatures through class group computations, in Advances in Cryptology–ASIACRYPT 2019–25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, December 8-12, 2019, Proceedings, Part I (eds. S. D. Galbraith and S. Moriai), vol. 11921 of Lecture Notes in Computer Science, Springer, 2019,227–247. [6] J.-F. Biasse, Improvements in the computation of ideal class groups of imaginary quadratic number fields, Adv. in Math. of Comm., 4 (2010), 141-154.  doi: 10.3934/amc.2010.4.141. [7] J.-F. Biasse, An L(1/3) algorithm for ideal class group and regulator computation in certain number fields, Math. Comp., 83 (2014), 2005-2031.  doi: 10.1090/S0025-5718-2014-02651-3. [8] J.-F. Biasse, Subexponential time relations in the class group of large degree number fields, Advances in Mathematics of Communications, 8 (2014), 407–425, http://aimsciences.org/journals/displayArticlesnew.jsp?paperID=10551. doi: 10.3934/amc.2014.8.407. [9] J. Biasse, T. Espitau, P. Fouque, A. Gélin and P. Kirchner, Computing generator in cyclotomic integer rings, in Advances in Cryptology–EUROCRYPT 2017–36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2017, Proceedings, Part I (eds. J. Coron and J. Nielsen), vol. 10210 of Lecture Notes in Computer Science, 2017, 60–88. doi: 10.1007/978-3-319-56620-7_3. [10] J.-F. Biasse and C. Fieker, Subexponential class group and unit group computation in large degree number fields, LMS Journal of Computation and Mathematics, 17 (2014), 385-403.  doi: 10.1112/S1461157014000345. [11] J.-F. Biasse, C. Fieker, T. Hofmann and A. Page, Norm relations and computational problems in number fields, 2020. [12] J.-F. Biasse, C. Fieker and M. Jacobson, Fast heuristic algorithms for computing relations in the class group of a quadratic order, with applications to isogeny evaluation, LMS Journal of Computation and Mathematics, 19 (2016), 371-390.  doi: 10.1112/S1461157016000358. [13] J.-F. Biasse and M. Jacobson, Practical improvements to class group and regulator computation of real quadratic fields, in Algorithmic Number Theory, 9th International Symposium, ANTS-IX, Nancy, France, July 19-23, 2010. Proceedings (eds. G. Hanrot, F. Morain and E. Thomé), vol. 6197 of Lecture Notes in Computer Science, Springer, 2010, 50–65. doi: 10.1007/978-3-642-14518-6_8. [14] J.-F. Biasse, M. J. Jr. and A. Silvester, Security estimates for quadratic field based cryptosystems, in Information Security and Privacy–15th Australasian Conference, ACISP 2010, Sydney, Australia, July 5-7, 2010. Proceedings (eds. R. Steinfeld and P. Hawkes), vol. 6168 of Lecture Notes in Computer Science, Springer, 2010,233–247. doi: 10.1007/978-3-642-14081-5_15. [15] J.-F. Biasse and F. Song, Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, 2016,893–902. doi: 10.1137/1.9781611974331.ch64. [16] J.-F. Biasse and C. van Vredendaal, Fast multiquadratic $S$-unit computation and application to the calculation of class groups, in Proceedings of ANTS XIII, 2 (2019), 103–118. [17] S. Birmpilis, G. Labahn and A. Storjohann, A las vegas algorithm for computing the smith form of a nonsingular integer matrix, in ISSAC '20: International Symposium on Symbolic and Algebraic Computation, Kalamata, Greece, July 20-23, 2020 (eds. I. Z. Emiris and L. Zhi), ACM, 2020, 38–45. doi: 10.1145/3373207.3404022. [18] J. Buchmann, A subexponential algorithm for the determination of class groups and regulators of algebraic number fields, in Séminaire de Théorie des Nombres, Paris 1988–1989 (ed. S. Goldstein), Birkhauser, Boston, 91 (1990), 27–41. [19] J. Buchmann and H. C. Williams, A key exchange system based on real quadratic fields, in Advances in Cryptology–CRYPTO '89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings (ed. G. Brassard), vol. 435 of Lecture Notes in Computer Science, Springer, 1989,335–343. doi: 10.1007/0-387-34805-0_31. [20] J. Buchmann and H. C. Williams, A key-exchange system based on imaginary quadratic fields, J. Cryptol., 1 (1988), 107-118.  doi: 10.1007/BF02351719. [21] H. Cohen, A course in computational algebraic number theory, Graduate texts in Math., 138 (1993), 88, https://ci.nii.ac.jp/naid/10006515766/en/. doi: 10.1007/978-3-662-02945-9. [22] H. Cohen, F. D. Y. Diaz and M. Olivier, Subexponential algorithms for class group and unit computations, Journal of Symbolic Computation, 24 (1997), 433-441.  doi: 10.1006/jsco.1996.0143. [23] E. D. Cristofaro, J. Kim and G. Tsudik, Linear-complexity private set intersection protocols secure in malicious model, in Advances in Cryptology–ASIACRYPT 2010–16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5-9, 2010. Proceedings (ed. M. Abe), vol. 6477 of Lecture Notes in Computer Science, Springer, 2010,213–231. [24] J. Hafner and K. McCurley, A rigorous subexponential algorithm for computation of class groups, Journal of the American Mathematical Society, 2 (1989), 837-850.  doi: 10.1090/S0894-0347-1989-1002631-0. [25] D. Jao, S. D. Miller and R. Venkatesan, Expander graphs based on GRH with an application to elliptic curve cryptography, J. Number Theory, 129 (2009), 1491-1504.  doi: 10.1016/j.jnt.2008.11.006. [26] M. J. J. Jr., Applying sieving to the computation of quadratic class groups, Math. Comput., 68 (1999), 859-867.  doi: 10.1090/S0025-5718-99-01003-0. [27] T. Kleinjung, Quadratic sieving, Math. Comput., 85 (2016), 1861-1873.  doi: 10.1090/mcom/3058. [28] A. Lenstra, On the calculation of regulators and class numbers of quadratic fields, in Journées Arithmétiques, Cambridge Univ. Press, 56 (1982), 123–150. [29] K. S. McCurley, Cryptographic key distribution and computation in class groups, in Number Theory and Applications (Banff, AB, 1988), vol. 265 of NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., Kluwer Acad. Publ., Dordrecht, 1989,459–479. [30] K. Pietrzak, Simple verifiable delay functions, in 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA (ed. A. Blum), vol. 124 of LIPIcs, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2019, Art. No. 60, 15 pp. doi: 10.4230/LIPIcs.ITCS.2019.60. [31] M. Pohst,  Algorithmic Methods in Algebra and Number Theory, 1, Academic Press, 1987. [32] O. Regev and N. Stephens-Davidowitz, A reverse minkowski theorem, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Association for Computing Machinery, New York, NY, USA, 2017,941–953. doi: 10.1145/3055399.3055434. [33] R. Schoof, Quadratic fields and factorization, Computational Methods in Number Theory, Part II, Math. Centre Tracts, Math. Centrum, Amsterdam, 155 (1982), 235–286. [34] M. Seysen, A probabilistic factorization algorithm with quadratic forms of negative discriminant, Mathematics of Computation, 48 (1987), 757-780.  doi: 10.1090/S0025-5718-1987-0878705-X. [35] D. Shanks, Class number, a theory of factorization, and genera, in Proceedings of Symposia in Pure Mathematics (eds. W. J. LeVeque and E. G. Straus), vol. 20, American Mathematical Society, 1971,415–440. [36] D. Shanks, The infrastructure of a real quadratic field and its applications, in Proceedings of the 1972 Number Theory Conference, American Mathematical Society, 1972,217–224. [37] A. Storjohann, The shifted number system for fast linear algebra on integer matrices, J. Complex., 21 (2005), 609-650.  doi: 10.1016/j.jco.2005.04.002. [38] U. Vollmer, Asymptotically fast discrete logarithms in quadratic number fields, in Algorithmic Number Theory, 4th International Symposium, ANTS-IV, Leiden, The Netherlands, July 2-7, 2000, Proceedings (ed. W. Bosma), vol. 1838 of Lecture Notes in Computer Science, Springer, 2000,581–594 doi: 10.1007/10722028_39. [39] U. Vollmer, An accelerated buchmann algorithm for regulator computation in real quadratic fields, in Algorithmic Number Theory, 5th International Symposium, ANTS-V, Sydney, Australia, July 7-12, 2002, Proceedings (eds. C. Fieker and D. R. Kohel), vol. 2369 of Lecture Notes in Computer Science, Springer, 2002,148–162 doi: 10.1007/3-540-45455-1_12. [40] B. Wesolowski, Efficient verifiable delay functions, J. Cryptology, 33 (2020), 2113-2147.  doi: 10.1007/s00145-020-09364-x.