# American Institute of Mathematical Sciences

November  2014, 8(4): 407-425. doi: 10.3934/amc.2014.8.407

## Subexponential time relations in the class group of large degree number fields

 1 Department of Computer Science, University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4, Canada

Received  January 2014 Revised  June 2014 Published  November 2014

Hafner and McCurley described a subexponential time algorithm to compute the ideal class group of a quadratic field, which was generalized to families of fixed degree number fields by Buchman. The main ingredient of this method is a subexponential time algorithm to derive relations between primes of norm bounded by a subexponential value. Besides ideal class group computation, this was successfully used to evaluate isogenies, compute endomorphism rings, solve the discrete logarithm problem in the class group and find a generator of a principal ideal. In this paper, we present a generalization of the relation search to classes of number fields with degree growing to infinity.
Citation: Jean-François Biasse. Subexponential time relations in the class group of large degree number fields. Advances in Mathematics of Communications, 2014, 8 (4) : 407-425. doi: 10.3934/amc.2014.8.407
##### References:
 [1] L. Adleman and J. DeMarrais, A subexponential algorithm for discrete logarithms over all finite fields,, in Adv. Crypt. - CRYPTO '93 (ed. D. Stinson), (1994), 147.  doi: 10.1007/3-540-48329-2_13.  Google Scholar [2] J.-F. Biasse, An $L(1/3)$ algorithm for ideal class group and regulator computation in certain number fields,, Math. Comp., 83 (2014), 2005.  doi: 10.1090/S0025-5718-2014-02651-3.  Google Scholar [3] J.-F. Biasse and C. Fieker, New techniques for computing the ideal class group and a system of fundamental units in number fields,, preprint, ().   Google Scholar [4] I. Biehl, J. Buchmann, S. Hamdy and A. Meyer, A signature scheme based on the intractability of computing roots,, Des. Codes Crypt., 25 (2002), 223.  doi: 10.1023/A:1014927327846.  Google Scholar [5] G. Bisson, Endomorphism Rings in Cryptography, Ph.D thesis,, LORIA, (2011).   Google Scholar [6] 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 (ed. C. Goldstein), (1990), 27.   Google Scholar [7] J. Buchmann and S. Paulus, A one way function based on ideal arithmetic in number fields,, in CRYPTO '97: Proc. 17th Annual Int. Crypt. Conf. Adv. Crypt., (1997), 385.   Google Scholar [8] J. Buchmann and U. Vollmer, Binary Quadratic Forms: An Algorithmic Approach,, Springer-Verlag, (2007).   Google Scholar [9] J. Buchmann and H. C. Williams, A key-exchange system based on real quadratic fields,, in CRYPTO '89, (1989), 335.  doi: 10.1007/0-387-34805-0_31.  Google Scholar [10] J. Cassels, An Introduction to the Geometry of Numbers,, Springer-Verlag, (1997).   Google Scholar [11] H. Cohen and H. W. Lenstra, Heuristics on class groups of number fields,, in Number Theory Noordwijkerhout 1983, (1983), 33.  doi: 10.1007/BFb0099440.  Google Scholar [12] A. Enge, P. Gaudry and E. Thomé, An $L(1/3)$ Discrete Logarithm Algorithm for Low Degree Curves,, available online at , ().   Google Scholar [13] C. Gentry, A Fully Homomorphic Encryption Scheme, Ph.D thesis,, Stanford University, (2009).   Google Scholar [14] C. Gentry, Fully homomorphic encryption using ideal lattices,, in Proc. 41st Annual ACM Symp. Theory Comp., (2009), 169.  doi: 10.1145/1536414.1536440.  Google Scholar [15] D. Gordon, Discrete logarithms in $GF(p)$ using the number field sieve,, SIAM J. Discrete Math., 6 (1993), 124.  doi: 10.1137/0406010.  Google Scholar [16] J. L. Hafner and K. S. McCurley, A rigorous subexponential algorithm for computation of class groups,, J. Amer. Math. Soc., 2 (1989), 837.  doi: 10.1090/S0894-0347-1989-1002631-0.  Google Scholar [17] G. Hanrot and D. Stehlé, Improved analysis of Kannans shortest lattice vector algorithm,, in Adv. Crypt. - CRYPTO 2007 (ed. A. Menezes), (2007), 170.  doi: 10.1007/978-3-540-74143-5_10.  Google Scholar [18] M. Jacobson, Á. Pintér and P. Walsh, A computational approach for solving $y^2 = 1^k + 2^k + \cdots + x^k$,, Math. Comp., 72 (2003), 2099.  doi: 10.1090/S0025-5718-03-01465-0.  Google Scholar [19] M. Jacobson and H. C. Williams, Solving the Pell Equation,, Springer-Verlag, (2009).   Google Scholar [20] D. Jao and V. Soukharev, A subexponential algorithm for evaluating large degree isogenies,, in Algorithmic Number Theory (eds. G. Hanrot, (2010), 219.  doi: 10.1007/978-3-642-14518-6_19.  Google Scholar [21] A. Joux, R. Lercier, N. P. Smart and F. Vercauteren, The number field sieve in the medium prime case,, in Adv. Cryptology - CRYPTO 2006 ed. C. Dwork, (2006), 326.  doi: 10.1007/11818175_19.  Google Scholar [22] N. Katz and P. Sarnak, Random Matrices, Frobenius Eigenvalues and Monodromy,, AMS, (1998).   Google Scholar [23] A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse and J. M. Pollard, The number field sieve,, in STOC '90: Proc 22nd Annual ACM Symp. Theory Computing, (1990), 564.  doi: 10.1145/100216.100295.  Google Scholar [24] J. E. Littlewood, On the class number of the corpus $P(\sqrtk)$,, Proc. London Math. Soc., 27 (1928), 358.  doi: 10.1112/plms/s2-27.1.358.  Google Scholar [25] D. Lubicz and D. Robert, Computing isogenies between abelian varieties,, Compositio Math., 148 (2012), 1483.  doi: 10.1112/S0010437X12000243.  Google Scholar [26] A. Meyer, S. Neis and T. Pfahler, First implementation of cryptographic protocols based on algebraic number fields,, in ACISP '01: Proc. 6th Australasian Conf. Inf. Sec. Privacy, (2001), 84.   Google Scholar [27] C. P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms,, Theor. Comp. Sci., 53 (1987), 201.  doi: 10.1016/0304-3975(87)90064-8.  Google Scholar [28] E. J. Scourfield, On ideals free of large prime factors,, J. Théorie Nombres Bordeaux, 16 (2004), 733.  doi: 10.5802/jtnb.468.  Google Scholar [29] N. Smart and F. Vercauteren, Fully homomorphic encryption with relatively small key and ciphertext sizes,, in Public Key Cryptography - PKC 2010 (eds. P. Nguyen and D. Pointcheval), (2010), 420.  doi: 10.1007/978-3-642-13013-7_25.  Google Scholar [30] U. Vollmer, Asymptotically fast discrete logarithms in quadratic number fields,, in Algorithmic Number Theory - ANTS-IV, (1838), 581.  doi: 10.1007/10722028_39.  Google Scholar

show all references

##### References:
 [1] L. Adleman and J. DeMarrais, A subexponential algorithm for discrete logarithms over all finite fields,, in Adv. Crypt. - CRYPTO '93 (ed. D. Stinson), (1994), 147.  doi: 10.1007/3-540-48329-2_13.  Google Scholar [2] J.-F. Biasse, An $L(1/3)$ algorithm for ideal class group and regulator computation in certain number fields,, Math. Comp., 83 (2014), 2005.  doi: 10.1090/S0025-5718-2014-02651-3.  Google Scholar [3] J.-F. Biasse and C. Fieker, New techniques for computing the ideal class group and a system of fundamental units in number fields,, preprint, ().   Google Scholar [4] I. Biehl, J. Buchmann, S. Hamdy and A. Meyer, A signature scheme based on the intractability of computing roots,, Des. Codes Crypt., 25 (2002), 223.  doi: 10.1023/A:1014927327846.  Google Scholar [5] G. Bisson, Endomorphism Rings in Cryptography, Ph.D thesis,, LORIA, (2011).   Google Scholar [6] 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 (ed. C. Goldstein), (1990), 27.   Google Scholar [7] J. Buchmann and S. Paulus, A one way function based on ideal arithmetic in number fields,, in CRYPTO '97: Proc. 17th Annual Int. Crypt. Conf. Adv. Crypt., (1997), 385.   Google Scholar [8] J. Buchmann and U. Vollmer, Binary Quadratic Forms: An Algorithmic Approach,, Springer-Verlag, (2007).   Google Scholar [9] J. Buchmann and H. C. Williams, A key-exchange system based on real quadratic fields,, in CRYPTO '89, (1989), 335.  doi: 10.1007/0-387-34805-0_31.  Google Scholar [10] J. Cassels, An Introduction to the Geometry of Numbers,, Springer-Verlag, (1997).   Google Scholar [11] H. Cohen and H. W. Lenstra, Heuristics on class groups of number fields,, in Number Theory Noordwijkerhout 1983, (1983), 33.  doi: 10.1007/BFb0099440.  Google Scholar [12] A. Enge, P. Gaudry and E. Thomé, An $L(1/3)$ Discrete Logarithm Algorithm for Low Degree Curves,, available online at , ().   Google Scholar [13] C. Gentry, A Fully Homomorphic Encryption Scheme, Ph.D thesis,, Stanford University, (2009).   Google Scholar [14] C. Gentry, Fully homomorphic encryption using ideal lattices,, in Proc. 41st Annual ACM Symp. Theory Comp., (2009), 169.  doi: 10.1145/1536414.1536440.  Google Scholar [15] D. Gordon, Discrete logarithms in $GF(p)$ using the number field sieve,, SIAM J. Discrete Math., 6 (1993), 124.  doi: 10.1137/0406010.  Google Scholar [16] J. L. Hafner and K. S. McCurley, A rigorous subexponential algorithm for computation of class groups,, J. Amer. Math. Soc., 2 (1989), 837.  doi: 10.1090/S0894-0347-1989-1002631-0.  Google Scholar [17] G. Hanrot and D. Stehlé, Improved analysis of Kannans shortest lattice vector algorithm,, in Adv. Crypt. - CRYPTO 2007 (ed. A. Menezes), (2007), 170.  doi: 10.1007/978-3-540-74143-5_10.  Google Scholar [18] M. Jacobson, Á. Pintér and P. Walsh, A computational approach for solving $y^2 = 1^k + 2^k + \cdots + x^k$,, Math. Comp., 72 (2003), 2099.  doi: 10.1090/S0025-5718-03-01465-0.  Google Scholar [19] M. Jacobson and H. C. Williams, Solving the Pell Equation,, Springer-Verlag, (2009).   Google Scholar [20] D. Jao and V. Soukharev, A subexponential algorithm for evaluating large degree isogenies,, in Algorithmic Number Theory (eds. G. Hanrot, (2010), 219.  doi: 10.1007/978-3-642-14518-6_19.  Google Scholar [21] A. Joux, R. Lercier, N. P. Smart and F. Vercauteren, The number field sieve in the medium prime case,, in Adv. Cryptology - CRYPTO 2006 ed. C. Dwork, (2006), 326.  doi: 10.1007/11818175_19.  Google Scholar [22] N. Katz and P. Sarnak, Random Matrices, Frobenius Eigenvalues and Monodromy,, AMS, (1998).   Google Scholar [23] A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse and J. M. Pollard, The number field sieve,, in STOC '90: Proc 22nd Annual ACM Symp. Theory Computing, (1990), 564.  doi: 10.1145/100216.100295.  Google Scholar [24] J. E. Littlewood, On the class number of the corpus $P(\sqrtk)$,, Proc. London Math. Soc., 27 (1928), 358.  doi: 10.1112/plms/s2-27.1.358.  Google Scholar [25] D. Lubicz and D. Robert, Computing isogenies between abelian varieties,, Compositio Math., 148 (2012), 1483.  doi: 10.1112/S0010437X12000243.  Google Scholar [26] A. Meyer, S. Neis and T. Pfahler, First implementation of cryptographic protocols based on algebraic number fields,, in ACISP '01: Proc. 6th Australasian Conf. Inf. Sec. Privacy, (2001), 84.   Google Scholar [27] C. P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms,, Theor. Comp. Sci., 53 (1987), 201.  doi: 10.1016/0304-3975(87)90064-8.  Google Scholar [28] E. J. Scourfield, On ideals free of large prime factors,, J. Théorie Nombres Bordeaux, 16 (2004), 733.  doi: 10.5802/jtnb.468.  Google Scholar [29] N. Smart and F. Vercauteren, Fully homomorphic encryption with relatively small key and ciphertext sizes,, in Public Key Cryptography - PKC 2010 (eds. P. Nguyen and D. Pointcheval), (2010), 420.  doi: 10.1007/978-3-642-13013-7_25.  Google Scholar [30] U. Vollmer, Asymptotically fast discrete logarithms in quadratic number fields,, in Algorithmic Number Theory - ANTS-IV, (1838), 581.  doi: 10.1007/10722028_39.  Google Scholar
 [1] Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141 [2] Thomas Alazard. A minicourse on the low Mach number limit. Discrete & Continuous Dynamical Systems - S, 2008, 1 (3) : 365-404. doi: 10.3934/dcdss.2008.1.365 [3] Arseny Egorov. Morse coding for a Fuchsian group of finite covolume. Journal of Modern Dynamics, 2009, 3 (4) : 637-646. doi: 10.3934/jmd.2009.3.637 [4] Naeem M. H. Alkoumi, Pedro J. Torres. Estimates on the number of limit cycles of a generalized Abel equation. Discrete & Continuous Dynamical Systems, 2011, 31 (1) : 25-34. doi: 10.3934/dcds.2011.31.25 [5] Zhimin Chen, Kaihui Liu, Xiuxiang Liu. Evaluating vaccination effectiveness of group-specific fractional-dose strategies. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021062 [6] Michael Grinfeld, Amy Novick-Cohen. Some remarks on stability for a phase field model with memory. Discrete & Continuous Dynamical Systems, 2006, 15 (4) : 1089-1117. doi: 10.3934/dcds.2006.15.1089 [7] Marco Cirant, Diogo A. Gomes, Edgard A. Pimentel, Héctor Sánchez-Morgado. On some singular mean-field games. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021006 [8] Seung-Yeal Ha, Jinwook Jung, Jeongho Kim, Jinyeong Park, Xiongtao Zhang. A mean-field limit of the particle swarmalator model. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2021011 [9] Jaume Llibre, Luci Any Roberto. On the periodic solutions of a class of Duffing differential equations. Discrete & Continuous Dynamical Systems, 2013, 33 (1) : 277-282. doi: 10.3934/dcds.2013.33.277 [10] Lekbir Afraites, Abdelghafour Atlas, Fahd Karami, Driss Meskine. Some class of parabolic systems applied to image processing. Discrete & Continuous Dynamical Systems - B, 2016, 21 (6) : 1671-1687. doi: 10.3934/dcdsb.2016017 [11] Graziano Crasta, Philippe G. LeFloch. Existence result for a class of nonconservative and nonstrictly hyperbolic systems. Communications on Pure & Applied Analysis, 2002, 1 (4) : 513-530. doi: 10.3934/cpaa.2002.1.513 [12] Tomáš Roubíček. An energy-conserving time-discretisation scheme for poroelastic media with phase-field fracture emitting waves and heat. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 867-893. doi: 10.3934/dcdss.2017044 [13] Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265 [14] Zhouxin Li, Yimin Zhang. Ground states for a class of quasilinear Schrödinger equations with vanishing potentials. Communications on Pure & Applied Analysis, 2021, 20 (2) : 933-954. doi: 10.3934/cpaa.2020298 [15] Samir Adly, Oanh Chau, Mohamed Rochdi. Solvability of a class of thermal dynamical contact problems with subdifferential conditions. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 91-104. doi: 10.3934/naco.2012.2.91 [16] Shiqiu Fu, Kanishka Perera. On a class of semipositone problems with singular Trudinger-Moser nonlinearities. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1747-1756. doi: 10.3934/dcdss.2020452 [17] Yahui Niu. A Hopf type lemma and the symmetry of solutions for a class of Kirchhoff equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021027 [18] Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027 [19] Dayalal Suthar, Sunil Dutt Purohit, Haile Habenom, Jagdev Singh. Class of integrals and applications of fractional kinetic equation with the generalized multi-index Bessel function. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021019 [20] Brahim Alouini. Finite dimensional global attractor for a class of two-coupled nonlinear fractional Schrödinger equations. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021013

2019 Impact Factor: 0.734