Abstract:Given an ideal in a number field, it is desirable in many situations
to find two elements that generate the ideal over the ring of the
integers of the field. Existing algorithms are either randomized,
or impractical at cryptographic sizes.
In the paper, we present a deterministic
polynomial time algorithm to find the two-element representation of
an ideal. For a monic irreducible integral polynomial \( f(x) \),
let \( K=\Q[x]/(f) \) be the number field, and
\( O_K \) be the integral closure. Our algorithm works when
the norm of the input ideal is co-prime to the index
\( [O_K:\Z[x]/f] \). In particular, it
handles all ideals for monogenic \( f(x) \),
a class that includes the cyclotomic polynomials widely used in
lattice based cryptography. A key technical ingredient in our
result is a generalized version of Dedekind criterion.
From: Qi Cheng [view email]
[v1]
Thu, 25 Jun 2026 13:10:04 UTC (15 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。