CS Paper Radar

Weak Unit Reducibility of the Eleventh Cyclotomic Field

Yiyang Chang

cs.CR math.NT ·submitted 2026-11-11 13:00 UTC · v1
theory

Abstract

We prove that the cyclotomic field $K_{11}=\mathbb{Q}(ζ_{11})$ is unit reducible but not strongly unit reducible. So every nonzero principal fractional ideal of $K_{11}$ has a generator that is a shortest nonzero vector. For $I=h\mathcal{O}_{K_{11}}$, every shortest nonzero vector $α\in I$ satisfies $N_{K_{11}/\mathbb{Q}}(α/h)\in\{1,11\}$. The proof uses Sigrist's Hermite bound for cyclic forms and an averaging identity for cyclotomic units. For principal ideals in $K_{11}$, ideal-SVP and the shortest-generator problem are polynomial-time equivalent.

Closest papers

Nearest neighbours by meaning across the whole index.

SVP Is NP-Hard for Some Rank-2 Cyclotomic Modules

cs.CC cs.CR ·2026-09-01 ·Jiaqi Liu, Yansong Feng, Yanbin Pan
theory similarity 0.59
Abstract

Let $q$ be an odd prime. Let $ζ_q$ be a primitive $q$th root of unity, and put $K=\mathbb{Q}(ζ_q)$, with ring of integers $\mathcal{O}_K=\mathbb{Z}[ζ_q]$. As $q$ ranges over odd primes, we prove that the decision version of the Shortest Vector Problem ($\mathsf{SVP}$) in the canonical $\ell_2$-norm is $\mathsf{NP}$-complete on full-rank free submodules of $\mathcal{O}_K^2$ by giving a deterministic polynomial-time many-one reduction from Exact Cover by 3-Sets (X3C). The module rank is fixed at two. The main obstacle is closure under the action of $\mathcal{O}_K$. A module containing a nonzero vector also contains every scalar multiple of that vector by a nonzero element of $\mathcal{O}_K$, and some of these multiples may be shorter. Three ideas overcome this obstacle. First, we map the Bennett--Peikert Reed--Solomon lattice to a principal cyclotomic ideal and use Wan's point-count estimates to prove that a coset of this ideal contains many binary coefficient representatives. Second, we construct a checker whose canonical squared norm encodes the X3C equations, with a controlled nonnegative error term. Third, the checker and a second module coordinate combine with a separation bound for ideal cosets to rule out short vectors in NO instances. Each constructed instance consists of an odd prime $q$, two integral generators whose $2\times2$ generator matrix has nonzero determinant, and an integer squared threshold. The construction also gives $\mathsf{NP}$-hardness of search-$\mathsf{SVP}$ under deterministic polynomial-time Turing reductions with at most one oracle call.

0.39

Admissible sets of integers in imaginary quadratic fields of class number 1

cs.DM math.NT ·2026-10-25 ·Daniel Shiu
theory similarity 0.56
Abstract · 25 pages, 8 figures

Let $\mathcal O_K$ be the ring of integers of a number field $K$. A finite subset $\mathcal H=\{η_1,\ldots,η_k\}\subset\mathcal O_K$ is said to be \emph{admissible} if for every prime ideal $\mathfrak p$ in $\mathcal O_K$, the reductions of the $η_i$ modulo $\mathfrak p$ do not represent every residue class. The diameter of a finite subset $S$ of $\mathcal O_K$ is defined to be \[\mathrm{diam}(S):= \max_{η_i,η_j\in S:η_i\neqη_j}|\mathcal N(η_i-η_j)|\] where $\mathcal N$ denotes the norm down to the rational field. This paper computationally investigates admissible subsets of rings of integers in imaginary quadratic fields of class number 1 (such as the Gaussian integers or the Eisenstein integers) that are large relative to their diameter. The motivation is twofold. Firstly, there is the improvement of results analogous to the question of an upper bound for the least gap between large rational primes, which has been one of the great number theoretic successes of the twenty-first century. A second motivation is that there is the opportunity to disprove a variation of the second Hardy-Littlewood conjecture. The calculations in the paper provide new records on the smallest distance between primes in the fields in question, and explicit counter-examples to a generalisation of the second Hardy-Littlewood conjecture in all bar one of the fields.

0.30

$\mathsf{SVP}_\infty$ Is NP-Hard for Power-of-two Cyclotomic Ideals

cs.CC ·2026-11-10 ·Yansong Feng, Jiaqi Liu, Hengyi Luo, Yanbin Pan
theory similarity 0.55
Abstract

We prove that exact decision-$\mathsf{SVP}$ in the coefficient $\ell_\infty$-norm is $\mathsf{NP}$-complete for principal ideals and free modules of rank two over the cyclotomic rings $R_n=\mathbb{Z}[X]/(X^n+1)$, where $n$ ranges over powers of two. For each case, we give a deterministic polynomial-time many-one reduction from the Subset Sum problem. For an instance with $s$ positive input integers, the output lattice has dimension $O(s)$. A solution to the original Subset Sum instance can be recovered in polynomial time from any nonzero output lattice vector of norm at most the specified bound. We also transfer these reductions from $R_n$ to the power-of-two cyclic rings $S_{2n}=\mathbb{Z}[X]/(X^{2n}-1)$. This gives $\mathsf{NP}$-completeness of decision-$\mathsf{SVP}$ in the coefficient $\ell_\infty$-norm for principal ideals and free modules of any fixed positive rank over these rings.

0.19

Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli

cs.CR quant-ph ·2026-09-28 ·Mathias Boucher, Pierre-Alain Fouque, Yixin Shen
similarity 0.55
Abstract

The Learning With Errors (LWE) problem is a fundamental assumption in post-quantum cryptography. Regev established a quantum reduction from LWE to the Dihedral Coset Problem (DCP). Later, Brakerski et al. introduced the Extrapolated Dihedral Coset Problem (EDCP), proving its equivalence to LWE. However, unlike DCP, EDCP no longer admits a coset structure. This limits the direct application of techniques for hidden subgroup problems. In this work, we introduce the Cyclotomic Coset Problem (CCP), a cyclotomic generalization of DCP that preserves an exact hidden-subgroup structure. Let $ζ_p$ be a primitive $p$-th root of unity, let $π=ζ_p-1$, and write $q=p^t$ and $L=t(p-1)$. We work over $R_q=\mathbb Z_q[ζ_p] \cong \mathbb Z[ζ_p]/(π^L)$, where the isomorphism follows from the total ramification identity $(p)=(π)^{p-1}$. We exploit the resulting $π$-adic ideal chain to construct a quantum sieve that successively reduces phase states modulo $π^{L},π^{L-1},\ldots,π$. For every fixed prime $p$ and modulus $q=p^t$, our algorithm solves the CCP in time and sample complexity $2^{O_p(\log n\log q)}$, using polynomial quantum space. The sieve also applies to uniform EDCP and Gaussian S|LWE>, yielding quasi-polynomial time algorithms for all the above problems when $q=\text{poly}(n)$. This extends the power-of-two EDCP sieve of Bai et al. (CRYPTO 2025) to a cyclotomic setting. However, we emphasize that our result does not, by itself, yield a quasi-polynomial-time algorithm for standard LWE, because the currently known reduction produces only a limited number of approximate CCP states.

0.22

Euclidean SVP is NP-hard for Cyclic Lattices

cs.CC ·2026-09-15 ·Daqing Wan
theory similarity 0.52
Abstract · 39 pages

We prove that exact Euclidean SVP is NP-hard under deterministic polynomial-time many-one reductions for full-rank cyclic integer lattices, equivalently full-rank ideals of $R_N:=\mathbb{Z}[X]/(X^N-1)$ in the coefficient norm. Hardness holds with $N=q-1$ for a varying odd prime $q$. As an application, we prove the same hardness for the algebraic class of NTRU-form lattices $\{(x,z)\in R_N^2:Hx\equiv z\pmod{QR_N}\}$, where $H,Q$ are unrestricted inputs. The decision problems are NP-complete, and the exact search problems are NP-hard under polynomial-time Turing reductions. No hardness claim is made for cryptographic NTRU parameter subclasses or key-generation distributions.

0.38

Equal Hamming Weights at Fixed Root Order and Applications to Constacyclic MDS Codes

cs.IT ·2026-10-31 ·Li Zhu, Hongfeng Wu
theory similarity 0.52
Abstract

For a fixed positive integer $n>1$, we study the prime powers $q$ coprime to $n$ for which all monic irreducible factors of $Φ_n$ over $\F_q$ have the same coefficient Hamming weight. Cyclotomic orbit coefficients give a finite, effective classification of these fields. Outside finitely many computable characteristics, every factor has the support of its characteristic-zero orbit polynomial; the uniform condition $p>2^{\varphi(n)}$ suffices. In each remaining characteristic, extension exponents reduce to divisors of $\ord_n(p)$, and an integer variance identity expressed by polynomial gcd degrees decides equal weight. The same coefficient data determine the full weight distribution. As an application, we prove that an MDS constacyclic code with an irreducible generator forces every irreducible polynomial of the same root order to have full support, including factors associated with different constacyclic constants. This yields a uniform gcd and norm obstruction. We develop its short-multiplier extension, give a prime-order cubic family, and establish an explicit quadratic-residue exclusion without a prime-square alphabet or a near-square length hypothesis.

0.20

New Construction of Power Functions with Low c-Differential Uniformity over Finite Fields

cs.IT ·2026-09-19 ·Zhiye Yang, Yan Wang, Keqin Feng
theory similarity 0.51
Abstract

This paper investigates the $c$-differential uniformity of power functions over finite fields, an important class of cryptographic functions with favorable differential properties. Specifically, for finite fields $\mathbb{F}_q$ satisfying $q-1=en$ with $e\ge 3$ and $e\mid n$, we prove that there exists $c\in\mathbb{F}_q\setminus\{0,1,ε,\dots,ε^{e-1}\}$, where $ε$ is an $e$-th primitive root of unity in $\mathbb{F}_q^*$, the constructed power functions $f(x)=x^{ln+1}$ with $1\le l\le e-1$ and $\gcd(l,e)=1$ satisfy the upper bound $Δ(f,c)\le e$, provided that certain cyclotomic conditions hold. We show that our conditions are mild; namely, such power functions can be constructed over infinitely many extension fields $\mathbb{F}_q$ of $\mathbb{F}_p$ for any given $e\ge 3$ and prime $p$ with $p\nmid e$. Furthermore, based on the Weil bound for multiplicative character sums, we prove that the obtained upper bound is tight for sufficiently large $q$, demonstrating the optimality of our results. We also analyze the special case $c=-1$ and derive simplified explicit conditions. In particular, we explicitly characterize the admissible parameters for the case $e=3$ and present concrete function examples for practical validation.

0.25

Cyclotomic polynomials with trinomial irreducible factors over finite fields

cs.IT math.NT ·2026-10-31 ·Li Zhu, Hongfeng Wu
similarity 0.50
Abstract

We classify the pairs $(q,n)$, where $q$ is a prime power, $n>1$, and $\gcd(n,q)=1$, for which every irreducible factor of $Φ_n(x)$ over $\F_q$ has exactly three nonzero terms. The positive support exponents of these factors have a common greatest common divisor, which gives a unique reduction by a power substitution. The reduced degree is two in odd characteristic and belongs to $\{2,3,4\}$ in characteristic two; the cubic and quartic cases arise by scalar substitution from the layers of orders $7$ and $15$. This yields necessary and sufficient arithmetic conditions on $(q,n)$ and explicit factorizations. Among the classified families, precisely those arising from quartic bases have a divisor layer containing an irreducible factor with more than three terms.

0.33