Scholarlink

Let  \(K = \mathbb {Q}(\sqrt{d_1}, \ldots , \sqrt{d_n})\) be a multiquadratic field of degree  \(m = 2^n\) , and  \(D = d_1 \cdot \ldots \cdot d_n\) . Assume also that  \(\log {D} = (\log {m})^{O(1)}\) . In this work, we prove that  \(\operatorname {Ideal-SVP}_\gamma \) can be solved for ideals of multiquadratic fields in heuristic quasi-polynomial time in m with approximation factor  \(\gamma = e^{\mathcal {\widetilde{O}}(m^{1/2})}\) . Our work is an extension of the the algorithm (and the experiments) of Bauch, Bernstein, de Valence, Lange, and van Vredendaal for principal ideals in real multiquadratic fields to the case of non-principal ideals in real and imaginary multiquadratic fields.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On Approx-SVP in Multiquadratic Ideal Lattices

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Semen Aleksandrovich Novoselov

摘要

Let  \(K = \mathbb {Q}(\sqrt{d_1}, \ldots , \sqrt{d_n})\) be a multiquadratic field of degree  \(m = 2^n\) , and  \(D = d_1 \cdot \ldots \cdot d_n\) . Assume also that  \(\log {D} = (\log {m})^{O(1)}\) . In this work, we prove that  \(\operatorname {Ideal-SVP}_\gamma \) can be solved for ideals of multiquadratic fields in heuristic quasi-polynomial time in m with approximation factor  \(\gamma = e^{\mathcal {\widetilde{O}}(m^{1/2})}\) . Our work is an extension of the the algorithm (and the experiments) of Bauch, Bernstein, de Valence, Lange, and van Vredendaal for principal ideals in real multiquadratic fields to the case of non-principal ideals in real and imaginary multiquadratic fields.