An algorithm for computing the Stickelberger elements for imaginary multiquadratic fields | Applied Discrete Mathematics. Supplement. 2020. № 13. DOI: 10.17223/2226308X/13/3

An algorithm for computing the Stickelberger elements for imaginary multiquadratic fields

In this paper we present an algorithm for computing the Stickelberger ideal for multiquadratic fields K = Q(Vdi, ..., л/^П), where d = 1 (mod 4) for i = 1,...,n and d's are pair-wise co-prime. Our result is based on the work of R. Kucera [J. Number Theory 56, 1996]. We systematize the ideas of this work, put them into explicit algorithms, prove their correctness and complexity. For 2ⁿ = [K : Q], our algorithm runs for time (9(2ⁿ). We hope that the obtained results will serve as the first step towards solving the shortest vector problem for ideals of multi-quadratic fields, which is the core problem in lattice-based cryptography.

Download file

Counter downloads: 109

Keywords

мультиквадратичные поля, идеал Штикельбергера, элемент Штикельбергера, задача поиска короткого вектора, multiquadratic number field, Stickelberger ideal, Stickelberger element, the shortest vector problem

Authors

Name	Organization	E-mail
Olefirenko D. O.	Immanuel Kant Baltic Federal University	denis_cooler_1@mail.ru
Kirshanova E. A.	Immanuel Kant Baltic Federal University	elenakirshanova@gmail.com
Malygina E. S.	Immanuel Kant Baltic Federal University	emalygina@kantiana.ru
Novoselov S. A.	Immanuel Kant Baltic Federal University	snovoselov@kantiana.ru

Всего: 4

References

Cramer R., Ducas L., and Wesolowski B. Short Stickelberger class relations and application to ideal-SVP // Advances in Cryptology - Eucrocrypt 2017. Springer, 2017. P. 324-348.

Bauch J., Bernstein D. J., de Valence H., et al. Short generators without quantum computers: The case of multiquadratics // Advances in Cryptology - EUROCRYPT 2017. Springer, 2017. P. 27-59.

Biasse J.-F. and Vredendaal C. Fast multiquadratic S-unit computation and application to the calculation of class groups // Open Book Series. 2019. V. 2. P. 103-118.

Kucera R. On the Stickelberger ideal and circular units of a compositum of quadratic fields // J. Number Theory. 1996. V. 56. No. 1. P. 139-166.

Sinnott W. On the Stickelberger ideal and the circular units of an Abelian field // Invent. Math. 1980. V. 62. P. 181-234.

Berndt B.C., Evans R. J., and Williams K.S. Topics in Commutative Ring Theory. N.Y.: Wiley, 1998.

Cohen H. and Stevenhagen P. Computational Class Field Theory. 2008. https://arxiv.org/ pdf/0802.3843.pdf