Improvements in the computation of ideal class groups of imaginary quadratic number fields

Previous Article
Optimization of the arithmetic of the ideal class group for genus 4 hyperelliptic curves over projective coordinates
AMC Home
This Issue
Next Article
Explicit 2-power torsion of genus 2 curves over finite fields

May 2010, 4(2): 141-154. doi: 10.3934/amc.2010.4.141

Improvements in the computation of ideal class groups of imaginary quadratic number fields

1.	LIX - École Polytechnique, 91128 Palaiseau, France

Received May 2009 Revised February 2010 Published May 2010

Abstract
Related Papers

We investigate improvements to the algorithm for the computation of ideal class groups described by Jacobson in the imaginary quadratic case. These improvements rely on the large prime strategy and a new method for performing the linear algebra phase. We achieve a significant speed-up and are able to compute ideal class groups with discriminants of 110 decimal digits in less than a week.

Keywords: Hermite normal form., Ideal class group, index calculus, Gaussian elimination, large prime variant.

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C3.

Citation: 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

[1]	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
[2]	Elisa Gorla, Maike Massierer. Index calculus in the trace zero variety. Advances in Mathematics of Communications, 2015, 9 (4) : 515-539. doi: 10.3934/amc.2015.9.515
[3]	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
[4]	Vivi Rottschäfer. Multi-bump patterns by a normal form approach. Discrete & Continuous Dynamical Systems - B, 2001, 1 (3) : 363-386. doi: 10.3934/dcdsb.2001.1.363
[5]	Todor Mitev, Georgi Popov. Gevrey normal form and effective stability of Lagrangian tori. Discrete & Continuous Dynamical Systems - S, 2010, 3 (4) : 643-666. doi: 10.3934/dcdss.2010.3.643
[6]	Dario Bambusi, A. Carati, A. Ponno. The nonlinear Schrödinger equation as a resonant normal form. Discrete & Continuous Dynamical Systems - B, 2002, 2 (1) : 109-128. doi: 10.3934/dcdsb.2002.2.109
[7]	Roberto Avanzi, Nicolas Thériault. A filtering method for the hyperelliptic curve index calculus and its analysis. Advances in Mathematics of Communications, 2010, 4 (2) : 189-213. doi: 10.3934/amc.2010.4.189
[8]	A. Katok and R. J. Spatzier. Nonstationary normal forms and rigidity of group actions. Electronic Research Announcements, 1996, 2: 124-133.
[9]	Virginie De Witte, Willy Govaerts. Numerical computation of normal form coefficients of bifurcations of odes in MATLAB. Conference Publications, 2011, 2011 (Special) : 362-372. doi: 10.3934/proc.2011.2011.362
[10]	Letizia Stefanelli, Ugo Locatelli. Kolmogorov's normal form for equations of motion with dissipative effects. Discrete & Continuous Dynamical Systems - B, 2012, 17 (7) : 2561-2593. doi: 10.3934/dcdsb.2012.17.2561
[11]	John Burke, Edgar Knobloch. Normal form for spatial dynamics in the Swift-Hohenberg equation. Conference Publications, 2007, 2007 (Special) : 170-180. doi: 10.3934/proc.2007.2007.170
[12]	Dongmei Zheng, Ercai Chen, Jiahong Yang. On large deviations for amenable group actions. Discrete & Continuous Dynamical Systems - A, 2016, 36 (12) : 7191-7206. doi: 10.3934/dcds.2016113
[13]	Yves Guivarc'h. On the spectrum of a large subgroup of a semisimple group. Journal of Modern Dynamics, 2008, 2 (1) : 15-42. doi: 10.3934/jmd.2008.2.15
[14]	Dariusz Skrenty. Absolutely continuous spectrum of some group extensions of Gaussian actions. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 365-378. doi: 10.3934/dcds.2010.26.365
[15]	Ilias S. Kotsireas, Christos Koukouvinos, Dimitris E. Simos. MDS and near-MDS self-dual codes over large prime fields. Advances in Mathematics of Communications, 2009, 3 (4) : 349-361. doi: 10.3934/amc.2009.3.349
[16]	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
[17]	Stefan Siegmund. Normal form of Duffing-van der Pol oscillator under nonautonomous parametric perturbations. Conference Publications, 2001, 2001 (Special) : 357-361. doi: 10.3934/proc.2001.2001.357
[18]	Sanming Liu, Zhijie Wang, Chongyang Liu. Proximal iterative Gaussian smoothing algorithm for a class of nonsmooth convex minimization problems. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 79-89. doi: 10.3934/naco.2015.5.79
[19]	Sigve Hovda. Closed-form expression for the inverse of a class of tridiagonal matrices. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 437-445. doi: 10.3934/naco.2016019
[20]	M. Matzeu, Raffaella Servadei. A variational approach to a class of quasilinear elliptic equations not in divergence form. Discrete & Continuous Dynamical Systems - S, 2012, 5 (4) : 819-830. doi: 10.3934/dcdss.2012.5.819

2018 Impact Factor: 0.879

American Institute of Mathematical Sciences