A short basis of the Stickelberger ideal of a cyclotomic field
HTML articles powered by AMS MathViewer
- by Olivier Bernard and Radan Kučera
- Math. Comp. 93 (2024), 887-909
- DOI: https://doi.org/10.1090/mcom/3863
- Published electronically: August 9, 2023
- HTML | PDF | Request permission
Abstract:
We exhibit an explicit short basis of the Stickelberger ideal of cyclotomic fields of any conductor $m$, i.e., a basis containing only short elements. An element $\sum _{\sigma \in G_m} \varepsilon _{\sigma }\sigma$ of the group ring $\mathbb {Z}[G_{m}]$, where $G_m$ is the Galois group of the field, is said to be short if all of its coefficients $\varepsilon _{\sigma }$ are $0$ or $1$.
As a direct practical consequence, we deduce from this short basis an explicit upper bound on the relative class number that is valid for any conductor. This basis also has several concrete applications, in particular for the cryptanalysis of the Shortest Vector Problem on Ideal Lattices.
References
- Patrick Browne, Ronan Egan, Fintan Hegarty, and Padraig Ó Catháin, A survey of the Hadamard maximal determinant problem, Electron. J. Combin. 28 (2021), no. 4, Paper No. 4.41, 35. MR 4395234, DOI 10.37236/10367
- Olivier Bernard and Adeline Roux-Langlois, Twisted-PHS: using the product formula to solve approx-SVP in ideal lattices, Advances in cryptology—ASIACRYPT 2020. Part II, Lecture Notes in Comput. Sci., vol. 12492, Springer, Cham, [2020] ©2020, pp. 349–380. MR 4210343, DOI 10.1007/978-3-030-64834-3_{1}2
- Ronald Cramer, Léo Ducas, and Benjamin Wesolowski, Mildly short vectors in cyclotomic ideal lattices in quantum polynomial time, J. ACM 68 (2021), no. 2, Art. 8, 26. MR 4267057, DOI 10.1145/3431725
- J. M. Gandhi and K. S. Williams, On certain sums of fractional parts, Arch. Math. (Basel) 25 (1974), 41–44. MR 347715, DOI 10.1007/BF01238638
- Radan Kučera, On bases of odd and even universal ordinary distributions, J. Number Theory 40 (1992), no. 3, 264–283. MR 1154040, DOI 10.1016/0022-314X(92)90002-7
- Radan Kučera, On bases of the Stickelberger ideal and of the group of circular units of a cyclotomic field, J. Number Theory 40 (1992), no. 3, 284–316. MR 1154041, DOI 10.1016/0022-314X(92)90003-8
- Radan Kučera, On the Stickelberger ideal and circular units of a compositum of quadratic fields, J. Number Theory 56 (1996), no. 1, 139–166. MR 1370199, DOI 10.1006/jnth.1996.0008
- E. E. Kummer, Über die Zerlegung der aus Wurzeln der Einheit gebildeten complexen Zahlen in ihre Primfactoren, J. Reine Angew. Math. 35 (1847), 327–367 (German). MR 1578599, DOI 10.1515/crll.1847.35.327
- S. Louboutin, Upper bounds on relative class numbers of cyclotomic fields, Math. Slovaca 64 (2014), no. 1, 21–26. MR 3174255, DOI 10.2478/s12175-013-0183-5
- Daniele Micciancio and Shafi Goldwasser, Complexity of lattice problems, The Kluwer International Series in Engineering and Computer Science, vol. 671, Kluwer Academic Publishers, Boston, MA, 2002. A cryptographic perspective. MR 2042139, DOI 10.1007/978-1-4615-0897-7
- Alice Pellet-Mary, Guillaume Hanrot, and Damien Stehlé, Approx-SVP in ideal lattices with pre-processing, Advances in cryptology—EUROCRYPT 2019. Part II, Lecture Notes in Comput. Sci., vol. 11477, Springer, Cham, 2019, pp. 685–716. MR 3964650, DOI 10.1007/978-3-030-17656-3_{2}
- René Schoof, Catalan’s conjecture, Universitext, Springer-Verlag London, Ltd., London, 2008. MR 2459823, DOI 10.1007/978-1-84800-185-5
- W. Sinnott, On the Stickelberger ideal and the circular units of a cyclotomic field, Ann. of Math. (2) 108 (1978), no. 1, 107–134. MR 485778, DOI 10.2307/1970932
- W. Sinnott, On the Stickelberger ideal and the circular units of an abelian field, Invent. Math. 62 (1980/81), no. 2, 181–234. MR 595586, DOI 10.1007/BF01389158
- Ladislav Skula, Some bases of the Stickelberger ideal, Math. Slovaca 43 (1993), no. 5, 541–571. MR 1273710
- Lawrence C. Washington, Introduction to cyclotomic fields, 2nd ed., Graduate Texts in Mathematics, vol. 83, Springer-Verlag, New York, 1997. MR 1421575, DOI 10.1007/978-1-4612-1934-7
Bibliographic Information
- Olivier Bernard
- Affiliation: Univ. Rennes, CNRS, IRISA, Campus universitaire de Beaulieu, 263 avenue du Général Leclerc – Bât 12, 35042 Rennes Cedex, France; and Thales, Service Cryptographie, 4 avenue des Louvresses, 92230 Gennevilliers, France
- ORCID: 0000-0002-3410-3134
- Email: olivier.bernard@normalesup.org
- Radan Kučera
- Affiliation: Faculty of Science, Masaryk University, Kotlářská 2, 611 37 Brno, Czech Republic
- ORCID: 0009-0004-9267-9774
- Email: kucera@math.muni.cz
- Received by editor(s): October 26, 2021
- Received by editor(s) in revised form: February 17, 2023, and April 19, 2023
- Published electronically: August 9, 2023
- Additional Notes: The first author was supported by the European Union PROMETHEUS project (Horizon 2020 Research and Innovation Program, grant 780701).
- © Copyright 2023 American Mathematical Society
- Journal: Math. Comp. 93 (2024), 887-909
- MSC (2020): Primary 11R18; Secondary 11R29, 11Y40
- DOI: https://doi.org/10.1090/mcom/3863
- MathSciNet review: 4678588