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]

in Adv. Crypt. - CRYPTO '93 (ed. D. Stinson), Springer, Berlin, 1994, 147-158. doi: 10.1007/3-540-48329-2_13.  Google Scholar

[2]

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]

Des. Codes Crypt., 25 (2002), 223-236. doi: 10.1023/A:1014927327846.  Google Scholar

[5]

LORIA, Nancy, 2011. Google Scholar

[6]

in Séminaire de Théorie des Nombres (ed. C. Goldstein), Birkhäuser, Boston, 1990, 27-41.  Google Scholar

[7]

in CRYPTO '97: Proc. 17th Annual Int. Crypt. Conf. Adv. Crypt., Springer-Verlag, London, 1997, 385-394. Google Scholar

[8]

Springer-Verlag, 2007.  Google Scholar

[9]

in CRYPTO '89, 1989, 335-343. doi: 10.1007/0-387-34805-0_31.  Google Scholar

[10]

Springer-Verlag, Berlin, 1997.  Google Scholar

[11]

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]

Stanford University, 2009. Google Scholar

[14]

in Proc. 41st Annual ACM Symp. Theory Comp., ACM, New York, 2009, 169-178. doi: 10.1145/1536414.1536440.  Google Scholar

[15]

SIAM J. Discrete Math., 6 (1993), 124-138. doi: 10.1137/0406010.  Google Scholar

[16]

J. Amer. Math. Soc., 2 (1989), 837-850. doi: 10.1090/S0894-0347-1989-1002631-0.  Google Scholar

[17]

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]

Math. Comp., 72 (2003), 2099-2110. doi: 10.1090/S0025-5718-03-01465-0.  Google Scholar

[19]

Springer-Verlag, 2009.  Google Scholar

[20]

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]

in Adv. Cryptology - CRYPTO 2006 ed. C. Dwork, Springer, 2006, 326-344. doi: 10.1007/11818175_19.  Google Scholar

[22]

AMS, 1998.  Google Scholar

[23]

in STOC '90: Proc 22nd Annual ACM Symp. Theory Computing, ACM, New York, 1990, 564-572. doi: 10.1145/100216.100295.  Google Scholar

[24]

Proc. London Math. Soc., 27 (1928), 358-372. doi: 10.1112/plms/s2-27.1.358.  Google Scholar

[25]

Compositio Math., 148 (2012), 1483-1515. doi: 10.1112/S0010437X12000243.  Google Scholar

[26]

in ACISP '01: Proc. 6th Australasian Conf. Inf. Sec. Privacy, Springer-Verlag, London, 2001, 84-103. Google Scholar

[27]

Theor. Comp. Sci., 53 (1987), 201-224. doi: 10.1016/0304-3975(87)90064-8.  Google Scholar

[28]

J. Théorie Nombres Bordeaux, 16 (2004), 733-772. doi: 10.5802/jtnb.468.  Google Scholar

[29]

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]

in Algorithmic Number Theory - ANTS-IV, 1838, 581-594. doi: 10.1007/10722028_39.  Google Scholar

show all references

References:
[1]

in Adv. Crypt. - CRYPTO '93 (ed. D. Stinson), Springer, Berlin, 1994, 147-158. doi: 10.1007/3-540-48329-2_13.  Google Scholar

[2]

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]

Des. Codes Crypt., 25 (2002), 223-236. doi: 10.1023/A:1014927327846.  Google Scholar

[5]

LORIA, Nancy, 2011. Google Scholar

[6]

in Séminaire de Théorie des Nombres (ed. C. Goldstein), Birkhäuser, Boston, 1990, 27-41.  Google Scholar

[7]

in CRYPTO '97: Proc. 17th Annual Int. Crypt. Conf. Adv. Crypt., Springer-Verlag, London, 1997, 385-394. Google Scholar

[8]

Springer-Verlag, 2007.  Google Scholar

[9]

in CRYPTO '89, 1989, 335-343. doi: 10.1007/0-387-34805-0_31.  Google Scholar

[10]

Springer-Verlag, Berlin, 1997.  Google Scholar

[11]

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]

Stanford University, 2009. Google Scholar

[14]

in Proc. 41st Annual ACM Symp. Theory Comp., ACM, New York, 2009, 169-178. doi: 10.1145/1536414.1536440.  Google Scholar

[15]

SIAM J. Discrete Math., 6 (1993), 124-138. doi: 10.1137/0406010.  Google Scholar

[16]

J. Amer. Math. Soc., 2 (1989), 837-850. doi: 10.1090/S0894-0347-1989-1002631-0.  Google Scholar

[17]

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]

Math. Comp., 72 (2003), 2099-2110. doi: 10.1090/S0025-5718-03-01465-0.  Google Scholar

[19]

Springer-Verlag, 2009.  Google Scholar

[20]

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]

in Adv. Cryptology - CRYPTO 2006 ed. C. Dwork, Springer, 2006, 326-344. doi: 10.1007/11818175_19.  Google Scholar

[22]

AMS, 1998.  Google Scholar

[23]

in STOC '90: Proc 22nd Annual ACM Symp. Theory Computing, ACM, New York, 1990, 564-572. doi: 10.1145/100216.100295.  Google Scholar

[24]

Proc. London Math. Soc., 27 (1928), 358-372. doi: 10.1112/plms/s2-27.1.358.  Google Scholar

[25]

Compositio Math., 148 (2012), 1483-1515. doi: 10.1112/S0010437X12000243.  Google Scholar

[26]

in ACISP '01: Proc. 6th Australasian Conf. Inf. Sec. Privacy, Springer-Verlag, London, 2001, 84-103. Google Scholar

[27]

Theor. Comp. Sci., 53 (1987), 201-224. doi: 10.1016/0304-3975(87)90064-8.  Google Scholar

[28]

J. Théorie Nombres Bordeaux, 16 (2004), 733-772. doi: 10.5802/jtnb.468.  Google Scholar

[29]

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]

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]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

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

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

Gabriella Tarantello. Analytical, geometrical and topological aspects of a class of mean field equations on surfaces. Discrete & Continuous Dynamical Systems, 2010, 28 (3) : 931-973. doi: 10.3934/dcds.2010.28.931

[18]

Pierluigi Colli, Danielle Hilhorst, Françoise Issard-Roch, Giulio Schimperna. Long time convergence for a class of variational phase-field models. Discrete & Continuous Dynamical Systems, 2009, 25 (1) : 63-81. doi: 10.3934/dcds.2009.25.63

[19]

Siting Liu, Levon Nurbekyan. Splitting methods for a class of non-potential mean field games. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021014

[20]

Simon Castle, Norbert Peyerimhoff, Karl Friedrich Siburg. Billiards in ideal hyperbolic polygons. Discrete & Continuous Dynamical Systems, 2011, 29 (3) : 893-908. doi: 10.3934/dcds.2011.29.893

2019 Impact Factor: 0.734

Metrics

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

Other articles
by authors

[Back to Top]