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

Jean-François Biasse

doi:10.3934/amc.2014.8.407

Article Contents

2014, Volume 8, Issue 4: 407-425. Doi: 10.3934/amc.2014.8.407

This issue Previous Article Comparison of scalar multiplication on real hyperelliptic curves Next Article Some remarks on primality proving and elliptic curves

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

Jean-François Biasse^1,

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

Received: January 2014

Revised: June 2014

Published: November 2014

Abstract / Introduction Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 11R11, 11R29, 11Y40; Secondary: 11Y16.

Citation:

Related Papers

Cited by

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.
[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.