Advanced Search
Article Contents
Article Contents

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

  • * Corresponding author: Jean-François Biasse

    * Corresponding author: Jean-François Biasse 

The first author is supported by NSF grant 1846166

Abstract Full Text(HTML) Related Papers Cited by
  • 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.


    \begin{equation} \\ \end{equation}
  • 加载中
  • [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. BiasseC. 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. CohenF. 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. JaoS. 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. PohstAlgorithmic 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.
  • 加载中

Article Metrics

HTML views(1989) PDF downloads(639) Cited by(0)

Access History



    DownLoad:  Full-Size Img  PowerPoint