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

Jean-François Biasse; Muhammed Rashad Erukulangara

doi:10.3934/amc.2021055

Article Contents

2023, Volume 17, Issue 6: 1388-1405. Doi: 10.3934/amc.2021055

This issue Previous Article Splitting authentication codes with perfect secrecy: New results, constructions and connections with algebraic manipulation detection codes Next Article Reversible $ G $-codes over the ring $ {\mathcal{F}}_{j,k} $ with applications to DNA codes

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

University of South Florida, Center for Cryptographic Research, 4202 E Fowler Ave, Tampa, FL 33620, USA

^* Corresponding author: Jean-François Biasse
^* Corresponding author: Jean-François Biasse

Received: July 2021

Revised: September 2021

Early access: November 2021

Published: December 2023

The first author is supported by NSF grant 1846166

Abstract / Introduction Full Text(HTML) Related Papers Cited by

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.

Keywords:

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

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[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.