Fugu-MT 論文翻訳(概要): Primitive-Root Determinant Densities over Prime Fields and Implications for PRIM-LWE

論文の概要: Primitive-Root Determinant Densities over Prime Fields and Implications for PRIM-LWE

arxiv url: http://arxiv.org/abs/2603.11196v1
Date: Wed, 11 Mar 2026 18:04:48 GMT
ステータス: 翻訳完了
システム内更新日: 2026-03-13 14:46:25.568543
Title: Primitive-Root Determinant Densities over Prime Fields and Implications for PRIM-LWE
Title（参考訳）: PRIM-LWEの原位置決定密度と意味
Authors: Vipin Singh Sehrawat,
Abstract要約: textscprim-lwe問題はLearningの変種であり、秘密行列にプリミティブ-ルート行列を持つ必要がある。我々は、$c(p)$ が素数上の連続純粋特異極限分布を持つことを証明する。素数$ple x$の最悪のオーバヘッドは$(loglog x)$、ポイントワイズ$/c(q)=O(loglog q)$である。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The \textsc{prim-lwe} problem (Sehrawat, Yeo, and Desmedt, \emph{Theoret.\ Comput.\ Sci.}\ 886, 2021) is a variant of Learning with Errors requiring the secret matrix to have a primitive-root determinant. The dimension-uniform reduction constant is $c(p)=\inf_{m\ge 1}c_m(p)$, where $c_n(p)$ is the density of $n\times n$ matrices over~$\mathbb{F}_p$ with primitive-root determinant. Those authors asked whether $\inf_{p\text{ prime}}c(p)=0$, noting that an affirmative answer would follow from the conjectural infinitude of primorial primes. We resolve this unconditionally using only Dirichlet's theorem and Mertens' product formula, bypassing the primorial-prime hypothesis entirely. We establish the sharp order $\min_{p\le x}c(p)\asymp 1/\log\log x$, prove that $c(p)$ possesses a continuous purely singular limiting distribution over the primes with support exactly $[0,1/2]$, and derive explicit lower bounds on $c(q)$ for primes of cryptographic interest parameterized solely by~$ω(q{-}1)$, the number of distinct prime factors of~$q{-}1$. These bounds apply to every prime~$q$ whose predecessor has controlled factorization structure, as measured by~$ω(q{-}1)$; this includes many NTT-friendly moduli, though NTT-friendliness alone does not imply the needed bound. For the NIST-standardized moduli $q=3329$ (ML-KEM) and $q=8380417$ (ML-DSA), the dimension-uniform expected rejection-sampling overhead~$1/c(q)$ is at most $2.17$ and $3.42$, respectively. As a simple conservative bound, for any prime $q>2^{30}$ one has $1/c(q)\le 1.79\log q$. The worst-case overhead among primes $p\le x$ is $Θ(\log\log x)$, and pointwise $1/c(q)=O(\log\log q)$.
Abstract（参考訳）: \textsc{prim-lwe} 問題(Sehrawat, Yeo, and Desmedt, \emph{Theoret)。計算。雪だるま。 }\ 886, 2021)はLearning with Errorsの変種である。次元-一様還元定数は$cである (p)=\inf_{m\ge 1}c_m (p)$, where $c_n (p)$はプリミティブ根行列式を持つ$n\times n$ matrices over~$\mathbb{F}_p$の密度である。これらの著者は$\inf_{p\text{ prime}}c を問うた。 (p)=0$ は、肯定的な答えは原始素数の客観的無限度から従うものである。我々はこれをディリクレの定理とメルテンスの積公式のみを用いて無条件に解決し、原始素数仮説を完全に無視する。シャープ順序 $\min_{p\le x}c を確立する。 (p)\asymp 1/\log\log x$, prove that $c (p)$は、ちょうど$[0,1/2]$をサポートする素数上の連続した純粋に特異な極限分布を持ち、$c 上の明示的な下界を導出する。 (q)$ は—$ω(q{-}1)$ でのみパラメータ化された暗号利子の素数に対して、~$q{-}1$ の異なる素因子の個数は~$q{-}1$ である。これらの境界は、前者が~$ω(q{-}1)$で測定されるように分解構造を制御しているすべての素数~$q$に適用できる。 NISTで標準化された moduli $q=3329$ (ML-KEM) と $q=8380417$ (ML-DSA) に対して、次元が一様で、予想される拒絶サンプリングのオーバーヘッド~1/c (q)$は、それぞれ2.17ドルと3.42ドルである。単純な保守的境界として、任意の素数$q>2^{30} に対して 1 は 1/c を持つ。 (q)\le 1.79\log q$。素数の最悪のオーバヘッドは$p\le x$ であり、ポイントワイズ1/cである。 (q)=O(\log\log) q)$。

論文の概要: Primitive-Root Determinant Densities over Prime Fields and Implications for PRIM-LWE

関連論文リスト