This article is cited in 1 paper

Theoretical Foundations of Applied Discrete Mathematics

An algorithm for computing the Stickelberger elements for imaginary multiquadratic fields

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

Immanuel Kant Baltic Federal University, Kaliningrad

Abstract: In this paper 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 $d_i \equiv 1 \pmod 4$ for $i=1,\ldots,n$ and $d_i$'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^n = [K : \mathbb{Q}]$, our algorithm runs for time $\widetilde{\mathcal{O}}(2^n)$. We hope that the obtained results will serve as the first step towards solving the shortest vector problem for ideals of multiquadratic fields, which is the core problem in lattice-based cryptography.

Keywords: multiquadratic number field, Stickelberger ideal, Stickelberger element, the shortest vector problem.

UDC: 511.48

DOI: 10.17223/2226308X/13/3