# 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

2018 Impact Factor: 0.879