Article Contents
Article Contents

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

• 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.
Mathematics Subject Classification: Primary: 11R11, 11R29, 11Y40; Secondary: 11Y16.

 Citation:

•  [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. [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. [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, arXiv:1204.1294 [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. [5] G. Bisson, Endomorphism Rings in Cryptography, Ph.D thesis, LORIA, Nancy, 2011. [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. [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. [8] J. Buchmann and U. Vollmer, Binary Quadratic Forms: An Algorithmic Approach, Springer-Verlag, 2007. [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. [10] J. Cassels, An Introduction to the Geometry of Numbers, Springer-Verlag, Berlin, 1997. [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. [12] A. Enge, P. Gaudry and E. Thomé, An $L(1/3)$ Discrete Logarithm Algorithm for Low Degree Curves, available online at http://hal.inria.fr/inria-00383941/PDF/L13.pdf [13] C. Gentry, A Fully Homomorphic Encryption Scheme, Ph.D thesis, Stanford University, 2009. [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. [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. [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. [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. [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. [19] M. Jacobson and H. C. Williams, Solving the Pell Equation, Springer-Verlag, 2009. [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. [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. [22] N. Katz and P. Sarnak, Random Matrices, Frobenius Eigenvalues and Monodromy, AMS, 1998. [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. [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. [25] D. Lubicz and D. Robert, Computing isogenies between abelian varieties, Compositio Math., 148 (2012), 1483-1515.doi: 10.1112/S0010437X12000243. [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. [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. [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. [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. [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.