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.11196v2
Date: Wed, 18 Mar 2026 17:17:03 GMT
ステータス: 翻訳完了
システム内更新日: 2026-03-19 16:03:46.716395
Title: Primitive-Root Determinant Densities over Prime Fields and Implications for PRIM-LWE
Title（参考訳）: PRIM-LWEの原位置決定密度と意味
Authors: Vipin Singh Sehrawat,
Abstract要約: PRIM-LWE問題はLearning with Errors問題の変種であり、秘密行列はプリミティブ・ルート行列式を持つ必要がある。素数上の$c(p)$の極限分布は、正確に$[0,1/2]$であることを示す。また、暗号的興味を持つ素数に対して$c(q)$の明示的な下限を導出し、q-1$の別個の素数だけによってパラメータ化する。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The PRIM-LWE problem, introduced by Sehrawat, Yeo, and Desmedt (Theoretical Computer Science, 886 (2021)), is a variant of the Learning with Errors problem in which the secret matrix is required to have a primitive-root determinant. The dimension-uniform reduction constant is $c(p)=\inf_{n\ge 1}c_n(p)$, where $c_n(p)$ is the exact density of $n\times n$ matrices over $\mathbb{F}_p$ with primitive-root determinant. Sehrawat, Yeo, and Desmedt asked whether $\inf_{p\text{ prime}} c(p)=0$, observing that an affirmative answer would follow from the conjectural infinitude of primorial primes. We resolve this question unconditionally using only Dirichlet's theorem and Mertens' product formula, entirely bypassing the primorial-prime hypothesis. We further establish the sharp order \[ \min_{p\le x} c(p)\asymp \frac{1}{\log\log x} \qquad (x\to\infty), \] and show that the limiting distribution of $c(p)$ over the primes has support exactly $[0,1/2]$. We have not found this full-support statement in the literature. The law coincides with the classical shifted-prime distribution of $\varphi(p-1)/(p-1)$ via a transport lemma and is moreover continuous and purely singular. We also derive explicit lower bounds on $c(q)$ for primes of cryptographic interest, parameterized solely by the number of distinct prime factors of $q-1$. As a simple conservative explicit bound, for any prime $q>2^{30}$ the expected overhead $1/c(q)$ is at most $1.79\log q$. On the other hand, our results show that the worst-case overhead among primes $p\le x$ is of order $Θ(\log\log x)$, and in particular $1/c(q)=O(\log\log q)$ pointwise.
Abstract（参考訳）: Sehrawat, Yeo, and Desmedt (Theoretical Computer Science, 886 (2021)) によって導入された PRIM-LWE 問題(英語版) は、秘密行列がプリミティブ・ルート決定因子を持つことが要求されるLearning with Errors 問題の変種である。次元-一様還元定数は$cである (p)=\inf_{n\ge 1}c_n (p)$, where $c_n (p)$はプリミティブ根行列式を持つ$\mathbb{F}_p$上の$n\times n$行列の正確な密度である。 Sehrawat, Yeo, Desmedt は $\inf_{p\text{ prime}} c を問うた。 (p)=0$は、肯定的な答えが原始素数の客観的無限度から従うことを観察する。この問題はディリクレの定理とメルテンスの積公式のみを用いて無条件に解決し、原始素数仮説を完全に回避する。さらにシャープ順序 \[ \min_{p\le x} c を確立する。 (p)\asymp \frac{1}{\log\log x} \qquad (x\to\infty), \] は$cの極限分布を示す。 (p)$ over the primes have correct $[0,1/2]$. 文献でこの完全支持の声明は見つからなかった。この法則は、輸送補題による$\varphi(p-1)/(p-1)$の古典的なシフト素数分布と一致し、さらに連続かつ純粋に特異である。また、$c 上の明示的な下限も導出します。 (q)$は暗号通貨の素数に対して、$q-1$の異なる素数だけによってパラメータ化される。単純な保守的明示的境界として、任意の素数$q>2^{30} に対して、期待されるオーバーヘッド1/c (q)$は少なくとも$1.79\log q$である。一方、この結果から、素数$p\le x$ の最悪のオーバヘッドは、次数$\(\log\log x)$ であり、特に 1/c であることがわかる。 (q)=O(\log\log) q)$ポイントワイズ。

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

関連論文リスト