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]

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

[3]

Thomas Alazard. A minicourse on the low Mach number limit. Discrete & Continuous Dynamical Systems - S, 2008, 1 (3) : 365-404. doi: 10.3934/dcdss.2008.1.365

[4]

Dandan Cheng, Qian Hao, Zhiming Li. Scale pressure for amenable group actions. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1091-1102. doi: 10.3934/cpaa.2021008

[5]

Christoforidou Amalia, Christian-Oliver Ewald. A lattice method for option evaluation with regime-switching asset correlation structure. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1729-1752. doi: 10.3934/jimo.2020042

[6]

Naeem M. H. Alkoumi, Pedro J. Torres. Estimates on the number of limit cycles of a generalized Abel equation. Discrete & Continuous Dynamical Systems, 2011, 31 (1) : 25-34. doi: 10.3934/dcds.2011.31.25

[7]

Arseny Egorov. Morse coding for a Fuchsian group of finite covolume. Journal of Modern Dynamics, 2009, 3 (4) : 637-646. doi: 10.3934/jmd.2009.3.637

[8]

Zhimin Chen, Kaihui Liu, Xiuxiang Liu. Evaluating vaccination effectiveness of group-specific fractional-dose strategies. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021062

[9]

Michael Grinfeld, Amy Novick-Cohen. Some remarks on stability for a phase field model with memory. Discrete & Continuous Dynamical Systems, 2006, 15 (4) : 1089-1117. doi: 10.3934/dcds.2006.15.1089

[10]

Marco Cirant, Diogo A. Gomes, Edgard A. Pimentel, Héctor Sánchez-Morgado. On some singular mean-field games. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021006

[11]

Seung-Yeal Ha, Jinwook Jung, Jeongho Kim, Jinyeong Park, Xiongtao Zhang. A mean-field limit of the particle swarmalator model. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2021011

[12]

Rafael López, Óscar Perdomo. Constant-speed ramps for a central force field. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3447-3464. doi: 10.3934/dcds.2021003

[13]

Joe Gildea, Adrian Korban, Abidin Kaya, Bahattin Yildiz. Constructing self-dual codes from group rings and reverse circulant matrices. Advances in Mathematics of Communications, 2021, 15 (3) : 471-485. doi: 10.3934/amc.2020077

[14]

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, 2021, 41 (8) : 3651-3682. doi: 10.3934/dcds.2021011

[15]

René Aïd, Roxana Dumitrescu, Peter Tankov. The entry and exit game in the electricity markets: A mean-field game approach. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021012

[16]

Jaume Llibre, Luci Any Roberto. On the periodic solutions of a class of Duffing differential equations. Discrete & Continuous Dynamical Systems, 2013, 33 (1) : 277-282. doi: 10.3934/dcds.2013.33.277

[17]

Lekbir Afraites, Abdelghafour Atlas, Fahd Karami, Driss Meskine. Some class of parabolic systems applied to image processing. Discrete & Continuous Dynamical Systems - B, 2016, 21 (6) : 1671-1687. doi: 10.3934/dcdsb.2016017

[18]

Graziano Crasta, Philippe G. LeFloch. Existence result for a class of nonconservative and nonstrictly hyperbolic systems. Communications on Pure & Applied Analysis, 2002, 1 (4) : 513-530. doi: 10.3934/cpaa.2002.1.513

[19]

Anderson L. A. de Araujo, Marcelo Montenegro. Existence of solution and asymptotic behavior for a class of parabolic equations. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1213-1227. doi: 10.3934/cpaa.2021017

[20]

Jia Li, Junxiang Xu. On the reducibility of a class of almost periodic Hamiltonian systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3905-3919. doi: 10.3934/dcdsb.2020268

2019 Impact Factor: 0.734

Metrics

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

Other articles
by authors

[Back to Top]