# 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), Springer, Berlin, 1994, 147-158. 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-2031. 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-236. doi: 10.1023/A:1014927327846.  Google Scholar [5] G. Bisson, Endomorphism Rings in Cryptography, Ph.D thesis, LORIA, Nancy, 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), Birkhäuser, Boston, 1990, 27-41.  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., Springer-Verlag, London, 1997, 385-394. 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-343. doi: 10.1007/0-387-34805-0_31.  Google Scholar [10] J. Cassels, An Introduction to the Geometry of Numbers, Springer-Verlag, Berlin, 1997.  Google Scholar [11] H. Cohen and H. W. Lenstra, Heuristics on class groups of number fields, in Number Theory Noordwijkerhout 1983, Springer-Verlag, New York, 1984, 33-62. 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., ACM, New York, 2009, 169-178. 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-138. 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-850. 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), Springer, Berlin, 2007, 170-186. 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-2110. 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, F. Morain and E. Thomé), Springer, Berlin, 2010, 219-233. 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, Springer, 2006, 326-344. 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, ACM, New York, 1990, 564-572. 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-372. 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-1515. 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, Springer-Verlag, London, 2001, 84-103. Google Scholar [27] C. P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theor. Comp. Sci., 53 (1987), 201-224. 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-772. 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), Springer, Berlin, 2010, 420-443. 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-594. 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), Springer, Berlin, 1994, 147-158. 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-2031. 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-236. doi: 10.1023/A:1014927327846.  Google Scholar [5] G. Bisson, Endomorphism Rings in Cryptography, Ph.D thesis, LORIA, Nancy, 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), Birkhäuser, Boston, 1990, 27-41.  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., Springer-Verlag, London, 1997, 385-394. 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-343. doi: 10.1007/0-387-34805-0_31.  Google Scholar [10] J. Cassels, An Introduction to the Geometry of Numbers, Springer-Verlag, Berlin, 1997.  Google Scholar [11] H. Cohen and H. W. Lenstra, Heuristics on class groups of number fields, in Number Theory Noordwijkerhout 1983, Springer-Verlag, New York, 1984, 33-62. 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., ACM, New York, 2009, 169-178. 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-138. 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-850. 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), Springer, Berlin, 2007, 170-186. 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-2110. 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, F. Morain and E. Thomé), Springer, Berlin, 2010, 219-233. 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, Springer, 2006, 326-344. 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, ACM, New York, 1990, 564-572. 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-372. 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-1515. 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, Springer-Verlag, London, 2001, 84-103. Google Scholar [27] C. P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theor. Comp. Sci., 53 (1987), 201-224. 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-772. 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), Springer, Berlin, 2010, 420-443. 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-594. 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] Rodrigo Abarzúa, Nicolas Thériault, Roberto Avanzi, Ismael Soto, Miguel Alfaro. Optimization of the arithmetic of the ideal class group for genus 4 hyperelliptic curves over projective coordinates. Advances in Mathematics of Communications, 2010, 4 (2) : 115-139. doi: 10.3934/amc.2010.4.115 [3] Laurent Imbert, Michael J. Jacobson, Jr., Arthur Schmidt. Fast ideal cubing in imaginary quadratic number and function fields. Advances in Mathematics of Communications, 2010, 4 (2) : 237-260. doi: 10.3934/amc.2010.4.237 [4] Jorge Garcia Villeda. A computable formula for the class number of the imaginary quadratic field $\mathbb Q(\sqrt{-p}), \ p = 4n-1$. Electronic Research Archive, 2021, 29 (6) : 3853-3865. doi: 10.3934/era.2021065 [5] David Karpuk, Anne-Maria Ernvall-Hytönen, Camilla Hollanti, Emanuele Viterbo. Probability estimates for fading and wiretap channels from ideal class zeta functions. Advances in Mathematics of Communications, 2015, 9 (4) : 391-413. doi: 10.3934/amc.2015.9.391 [6] Mike Boyle, Sompong Chuysurichay. The mapping class group of a shift of finite type. Journal of Modern Dynamics, 2018, 13: 115-145. doi: 10.3934/jmd.2018014 [7] Palash Sarkar, Shashank Singh. A unified polynomial selection method for the (tower) number field sieve algorithm. Advances in Mathematics of Communications, 2019, 13 (3) : 435-455. doi: 10.3934/amc.2019028 [8] Yi An, Zhuohan Li, Changzhi Wu, Huosheng Hu, Cheng Shao, Bo Li. Earth pressure field modeling for tunnel face stability evaluation of EPB shield machines based on optimization solution. Discrete & Continuous Dynamical Systems - S, 2020, 13 (6) : 1721-1741. doi: 10.3934/dcdss.2020101 [9] João Paulo da Silva, Julio López, Ricardo Dahab. Isogeny formulas for Jacobi intersection and twisted hessian curves. Advances in Mathematics of Communications, 2020, 14 (3) : 507-523. doi: 10.3934/amc.2020048 [10] Shunfu Jin, Wuyi Yue. Performance analysis and evaluation for power saving class type III in IEEE 802.16e network. Journal of Industrial & Management Optimization, 2010, 6 (3) : 691-708. doi: 10.3934/jimo.2010.6.691 [11] Yves Achdou, Manh-Khang Dao, Olivier Ley, Nicoletta Tchou. A class of infinite horizon mean field games on networks. Networks & Heterogeneous Media, 2019, 14 (3) : 537-566. doi: 10.3934/nhm.2019021 [12] Carla Mascia, Massimiliano Sala, Irene Villa. A survey on functional encryption. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021049 [13] Wenxian Shen. Global attractor and rotation number of a class of nonlinear noisy oscillators. Discrete & Continuous Dynamical Systems, 2007, 18 (2&3) : 597-611. doi: 10.3934/dcds.2007.18.597 [14] Jinliang Wang, Hongying Shu. Global analysis on a class of multi-group SEIR model with latency and relapse. Mathematical Biosciences & Engineering, 2016, 13 (1) : 209-225. doi: 10.3934/mbe.2016.13.209 [15] Jean-François Biasse, Muhammed Rashad Erukulangara. A proof of the conjectured run time of the Hafner-McCurley class group algorithm. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021055 [16] Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, 2021, 20 (1) : 449-465. doi: 10.3934/cpaa.2020276 [17] Xueyan Wu. An algorithm for reversible information hiding of encrypted medical images in homomorphic encrypted domain. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1441-1455. doi: 10.3934/dcdss.2019099 [18] Angsuman Das, Avishek Adhikari, Kouichi Sakurai. Plaintext checkable encryption with designated checker. Advances in Mathematics of Communications, 2015, 9 (1) : 37-53. doi: 10.3934/amc.2015.9.37 [19] Debrup Chakraborty, Sebati Ghosh, Cuauhtemoc Mancillas López, Palash Sarkar. ${\sf {FAST}}$: Disk encryption and beyond. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020108 [20] Reza Kaboli, Shahram Khazaei, Maghsoud Parviz. On ideal and weakly-ideal access structures. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021017

2020 Impact Factor: 0.935