Geodesic
On ideal class group computation of imaginary multiquadratic fields
Prikladnaâ diskretnaâ matematika, no. 4 (2022), pp. 22-30.

Voir la notice de l'article provenant de la source Math-Net.Ru

In the paper, we extend Biasse — van Vredendaal (OBS, 2019, vol. 2) implementation and experiments of the class group computation from real to imaginary multiquadratic fields. The implementation is optimized by introducing an explicit prime ideal lift operation and by using LLL reduction instead of HNF computation. We provide examples of class group computation of the imaginary multiquadratic fields of degree 64 and 128, that has been previously unreachable.
Keywords: multiquadratic field, ideal class group. 
@article{PDM_2022_4_a2,
     author = {S. A. Novoselov},
     title = {On ideal class group computation of imaginary multiquadratic fields},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {22--30},
     publisher = {mathdoc},
     number = {4},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/PDM_2022_4_a2/}
}
TY  - JOUR
AU  - S. A. Novoselov
TI  - On ideal class group computation of imaginary multiquadratic fields
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2022
SP  - 22
EP  - 30
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2022_4_a2/
LA  - en
ID  - PDM_2022_4_a2
ER  - 
%0 Journal Article
%A S. A. Novoselov
%T On ideal class group computation of imaginary multiquadratic fields
%J Prikladnaâ diskretnaâ matematika
%D 2022
%P 22-30
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2022_4_a2/
%G en
%F PDM_2022_4_a2
S. A. Novoselov. On ideal class group computation of imaginary multiquadratic fields. Prikladnaâ diskretnaâ matematika, no. 4 (2022), pp. 22-30. http://geodesic.mathdoc.fr/item/PDM_2022_4_a2/

[1] Buchmann J. and Paulus S., “A one way function based on ideal arithmetic in number fields”, LNCS, 1294, 1997, 385–394

[2] Biehl I., Buchmann J., Hamdy S., and Meyer A., “A signature scheme based on the intractability of computing roots”, Des. Codes Cryptogr., 25 (2002), 223–236 | DOI | MR

[3] Meyer A., Neis S., and Pfahler T., “First implementation of cryptographic protocols based on algebraic number fields”, LNCS, 2119, 2001, 84–103

[4] Lyubashevsky V., Peikert C., and Regev O., “On ideal lattices and learning with errors over rings”, LNCS, 6110, 2010, 1–23 | MR

[5] Lyubashevsky V. and Micciancio D., “Generalized compact knapsacks are collision resistant”, LNCS, 4052, 2006, 144–155 | MR

[6] Bauch J., Bernstein D. J., de Valence H., et al., “Short generators without quantum computers: the case of multiquadratics”, Ann. Intern. Conf. on the Theory and Applications of Cryptographic Techniques, LNSC, 10210, 2017, 27–59 https://multiquad.cr.yp.to/software.html | MR

[7] Pellet-Mary A., Hanrot G., and Stehlé D., “Approx-SVP in ideal lattices with pre-processing”, LNCS, 11477, 2019, 685–716 | MR

[8] Bernard O. and Roux-Langlois A., “Twisted-PHS — Using the product formula to solve Approx-SVP in ideal lattices”, LNCS, 12492, 2020, 349–380 | MR

[9] Buchmann J., “A subexponential algorithm for the determination of class groups and regulators of algebraic number fields”, Séminaire de Théorie des Nombres (Paris 1988/1989), Progr. Math., 91, Birkhäuser, Boston, 1990, 27–41 | MR

[10] Cohen H., Diaz Y Diaz F., and Olivier M., “Subexponential algorithms for class group and unit computations”, J. Symbolic Computation, 24 (1997), 433–441 | DOI | MR

[11] Biasse J.-F., An L(1/3) Algorithm for Discrete Logarithm Computation and Principality Testing in Certain Number Fields, 2012, arXiv: 1204.1292

[12] Biasse J.-F. and van Vredendaal C., “Fast multiquadratic S-unit computation and application to the calculation of class groups”, The Open Book Series, 2 (2019), 103–118 https://scarecryptow.org/publications/multiclass.html | DOI | MR

[13] Lenstra A. K., Lenstra H. W., and Lovasz L., “Factoring polynomials with rational coefficients”, Math. Ann., 261 (1982), 515–534 | DOI | MR

[14] Bach E., “Explicit bounds for primality testing and related problems”, Mathematics of Computation, 55:191 (1990), 355–380 | DOI | MR

[15] Grenié L. and Molteni G., “Explicit bounds for primality testing and related problems”, Mathematics of Computation, 2018, no. 313, 2483–2511

[16] Cohen H., A Course in Computational Algebraic Number Theory, Springer Verlag, Berlin, 1993 | MR

[17] Bach E., “Improved approximations for Euler products”, Number Theory, CMS Conf. Proc., 15, 1995, 13–28 | MR

[18] Belabas K. and Friedman E., “Computing the residue of the Dedekind zeta function”, Mathematics of Computation, 84:291 (2015), 357–369 | DOI | MR

[19] Fieker C., Hart W., Hofmann T., and Johansson F., “Nemo/Hecke: computer algebra and number theory packages for the Julia programming language”, Proc. ISSAC'17, 2017, 157–164 https://www.thofma.com/Hecke.jl/dev/ | MR

[20] Bezanson J., Edelman A., Karpinski S., and Shah V. B., “Julia: A fresh approach to numerical computing”, SIAM Review, 59:1 (2017), 65–98 | DOI | MR

[21] Cohen H., Advanced Topics in Computational Number Theory, Springer Science + Business Media, N.Y., 2000 | MR

[22] The Sage Developers, SageMath, the Sage Mathematics Software System (Version 9.4), 2022 https://www.sagemath.org