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]

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

[2]

Shuyang Dai, Fengru Wang, Jerry Zhijian Yang, Cheng Yuan. A comparative study of atomistic-based stress evaluation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020322

[3]

Karan Khathuria, Joachim Rosenthal, Violetta Weger. Encryption scheme based on expanded Reed-Solomon codes. Advances in Mathematics of Communications, 2021, 15 (2) : 207-218. doi: 10.3934/amc.2020053

[4]

Pierre-Etienne Druet. A theory of generalised solutions for ideal gas mixtures with Maxwell-Stefan diffusion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020458

[5]

Kalikinkar Mandal, Guang Gong. On ideal $ t $-tuple distribution of orthogonal functions in filtering de bruijn generators. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020125

[6]

Laurent Di Menza, Virginie Joanne-Fabre. An age group model for the study of a population of trees. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020464

[7]

Qiao Liu. Local rigidity of certain solvable group actions on tori. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 553-567. doi: 10.3934/dcds.2020269

[8]

Kien Trung Nguyen, Vo Nguyen Minh Hieu, Van Huy Pham. Inverse group 1-median problem on trees. Journal of Industrial & Management Optimization, 2021, 17 (1) : 221-232. doi: 10.3934/jimo.2019108

[9]

Meihua Dong, Keonhee Lee, Carlos Morales. Gromov-Hausdorff stability for group actions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1347-1357. doi: 10.3934/dcds.2020320

[10]

Yancong Xu, Lijun Wei, Xiaoyu Jiang, Zirui Zhu. Complex dynamics of a SIRS epidemic model with the influence of hospital bed number. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021016

[11]

Tomáš Bodnár, Philippe Fraunié, Petr Knobloch, Hynek Řezníček. Numerical evaluation of artificial boundary condition for wall-bounded stably stratified flows. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 785-801. doi: 10.3934/dcdss.2020333

[12]

Yi-Long Luo, Yangjun Ma. Low Mach number limit for the compressible inertial Qian-Sheng model of liquid crystals: Convergence for classical solutions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 921-966. doi: 10.3934/dcds.2020304

[13]

Juntao Sun, Tsung-fang Wu. The number of nodal solutions for the Schrödinger–Poisson system under the effect of the weight function. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021011

[14]

Hongyan Guo. Automorphism group and twisted modules of the twisted Heisenberg-Virasoro vertex operator algebra. Electronic Research Archive, , () : -. doi: 10.3934/era.2021008

[15]

Xiyou Cheng, Zhitao Zhang. Structure of positive solutions to a class of Schrödinger systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020461

[16]

Nguyen Thi Kim Son, Nguyen Phuong Dong, Le Hoang Son, Alireza Khastan, Hoang Viet Long. Complete controllability for a class of fractional evolution equations with uncertainty. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020104

[17]

Dandan Wang, Xiwang Cao, Gaojun Luo. A class of linear codes and their complete weight enumerators. Advances in Mathematics of Communications, 2021, 15 (1) : 73-97. doi: 10.3934/amc.2020044

[18]

Nahed Naceur, Nour Eddine Alaa, Moez Khenissi, Jean R. Roche. Theoretical and numerical analysis of a class of quasilinear elliptic equations. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 723-743. doi: 10.3934/dcdss.2020354

[19]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018

[20]

Illés Horváth, Kristóf Attila Horváth, Péter Kovács, Miklós Telek. Mean-field analysis of a scaling MAC radio protocol. Journal of Industrial & Management Optimization, 2021, 17 (1) : 279-297. doi: 10.3934/jimo.2019111

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (53)
  • HTML views (0)
  • Cited by (9)

Other articles
by authors

[Back to Top]