An algorithm for computing the Stickelberger ideal for multiquadratic number fields

E. A. Kirshanova ; E. S. Malygina ; S. A. Novoselov ; D. O. Olefirenko

Prikladnaâ diskretnaâ matematika, no. 1 (2021), pp. 9-30.

Résumé

We present an algorithm for computing the Stickelberger ideal for multiquadratic fields $K=\mathbb{Q}(\sqrt{d_1}, \sqrt{d_2},\ldots,\sqrt{d_n})$, where the integers $d_i \equiv 1 \bmod 4$ for $i \in \{1, \ldots, n\} $ or $d_j \equiv 2 \bmod 8$ for one $j \in \{1, \ldots, n \}$; all $d_i$'s are pairwise co-prime and square-free. Our result is based on the paper of Kučera [J. Number Theory, no. 56, 1996]. The algorithm we present works in time $\mathcal{O}(\lg \Delta_K \cdot 2^n \cdot \mathrm{poly}(n) )$, where $\Delta_K$ is the discriminant of $K$. As an interesting application, we show a connection between Stickelberger ideal and the class number of a multiquadratic field.

Détail

Keywords: multiquadratic number field, Stickelberger element, Stickelberger ideal, class group of multiquadratic field.

Bibliographie

[1] L. Stickelberger, “Über eine Verallgemeinerung der Kreistheilung”, Math. Ann., 37:3 (1890), 312–367 | DOI | MR

[2] L. C. Washington, Introduction to Cyclotomic Fields, Springer, 1997 | MR | Zbl

[3] R. Denomme, A History of Stickelberger's Theorem, The Ohio State University, 2009 https://core.ac.uk/download/pdf/159568254.pdf

[4] R. Cramer, L. Ducas, B. Wesolowski, “Short Stickelberger class relations and application to ideal-SVP”, EUROCRYPT 2017, LNCS, 10210, 2017, 324–348 | MR | Zbl

[5] B. Wesolowski, “Efficient verifiable delay functions”, EUROCRYPT 2019, LNCS, 11478, 2019, 379–407 | MR | Zbl

[6] K. Pietrzak, “Simple verifiable delay functions”, Innovations in Theoretical Computer Science Conference, ITCS 2019, 1–60 | MR

[7] A. Pedrouzo-Ulloa, J. R. Troncoso-Pastoriza, N. Gama et al., Revisiting Multivariate Ring Learning with Errors and its Applications on Lattice-based Cryptography, IACR Cryptol. ePrint Arch. 2019/1109

[8] R. Kučera, “On the Stickelberger ideal and circular units of a compositum of quadratic fields”, J. Number Theory, 56:1 (1996), 139–166 | DOI | MR

[9] Olefirenko D. O., Kirshanova E. A., Malygina E. S., Novoselov S. A., “An algorithm for computing the Stickelberger elements for imaginary multiquadratic fields”, Prikladnaya Diskretnaya Matematika. Prilozhenie, 2020, no. 13, 12–17 (in Russian)

[10] B. Schmal, “Diskriminanten, $\mathbb{Z}$-anzheitsbasen und relative Ganzheitsbasen bei multiquadratischen Zahlkörpern”, Archiv der Mathematik, 52:3 (1989), 245–257 | DOI | MR | Zbl

[11] W. Sinnott, “On the Stickelberger ideal and the circular units of an Abelian field”, Inventiones Mathematicae, 62 (1980), 181–234 | DOI | MR | Zbl

[12] B. C. Berndt, R. J. Evans, K. S. Williams, Gauss and Jacobi sums, Wiley, N.Y., 1998 | MR | Zbl

[13] S. Lang, Cyclotomic Fields, v. I, II, Springer, N.Y., 1990 | MR | Zbl

[14] J. Milne, Class field theory, v4.03, 2020 www.jmilne.org/math | Zbl

[15] S. Weintraub, Galois Theory, Second Ed., Springer, 2009 | MR | Zbl

[16] C. Aebi, G. Cairns, Sums of quadratic residues and nonresidues, 2015, arXiv: 1512.00896 | MR

[17] H. Cohen, A Course in Computational Algebraic Number Theory, Springer Verlag, 1995 | MR

[18] R. Brauer, “On the zeta-function of algebraic number fields”, Amer. J. Math., 69:2 (1947), 243–250 | DOI | MR | Zbl

[19] C. L. Siegel, “Uber die Classenzahl quadratischer Zahlkörper”, Acta Arithmetica, 1:1 (1935), 83–86 | DOI

[20] J. L. Hafner, K. S. McCurley, “A rigorous subexponential algorithm for computation of class groups”, J. Amer. Math. Soc., 2:4 (1989), 837–850 | DOI | MR | Zbl

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

[22] J. F. Biasse, C. Van Vredendaal, “Fast multiquadratic S-unit computation and application to the calculation of class groups”, Proc. ANTS XIII, 2019, 103–118 | MR

[23] H. Cohen, H. W. Lenstra, “Heuristics on class groups of number fields”, Number Theory Noordwijkerhout, Lecture Notes in Math., 1068, 1983, 33–62 | MR

[24] H. Cohen, J. Martinet, “Class groups of number fields: numerical heuristics”, Math. Comp., 48:177 (1987), 123–137 | DOI | MR | Zbl

[25] P. Schmid, “The Stickelberger element of an imaginary quadratic field”, Acta Arithmetica, 91:2 (1999), 165–169 | DOI | MR | Zbl

[26] T. Kubota, “Über den bizyklischen biquadratischen Zahlkörper”, Nagoya Math. J., 1956, no. 10, 65–85 | DOI | MR | Zbl

[27] J. Bauch, D. J. Bernstein, H. de Valence et al., “Short generators without quantum computers: The case of multiquadratics”, EUROCRYPT 2017, LNCS, 10210, 2017, 27–59 | MR | Zbl

[28] A. Bhand, M. Ram Murty, “Class numbers of quadratic fields”, Hardy-Ramanujan J., 42 (2019), 1–9 | MR

[29] H. Sato, “On class number formula for the real quadratic fields”, Proc. Japan Acad. Ser. A. Math. Sci., 80:7 (2004), 129–130 | DOI | MR | Zbl

[30] K. Ono, “Indivisibility of class numbers of real quadratic fields”, Compositio Mathematica, 119 (1999), 1–11 | DOI | MR | Zbl

[31] R. Mollin, H. Williams, “On a determination of real quadratic fields of class number one and related continues fraction period length less than 25”, Proc. Japan Acad. Ser. A. Math. Sci., 67 (1991), 20–25 | MR | Zbl

[32] R. Mollin, H. Williams, “On real quadratic fields of class number two”, Mathemat. Comput., 59:200 (1992), 625–632 | DOI | MR | Zbl

[33] H. Kuroda, “Uber die Klassenzahlen algebraischer Zahlkörper”, Nagoya Math. J., 1 (1950), 1–10 | DOI | MR | Zbl

[34] G. Herglotz, “Uber einen Dirichletschen Satz”, Mathematische Zeitschrift, 12:1 (1922), 255–261 | DOI | MR | Zbl

[35] E. Benjamin, F. Lemmermeyer, C. Snyder, “On the unit group of some multiquadratic number fields”, Pacific J. Math., 230 (2007), 27–40 | DOI | MR | Zbl

[36] A. Feaver, “Imaginary multiquadratic fields of class number 1”, J. Number Theory, 174 (2017), 93–117 | DOI | MR | Zbl