Fugu-MT 論文翻訳(概要): Bounds on polynomial approximations of the discrete logarithm function

論文の概要: Bounds on polynomial approximations of the discrete logarithm function

arxiv url: http://arxiv.org/abs/2610.33452v1
Date: Sat, 24 Oct 2026 05:13:45 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-27 22:27:13.332699
Title: Bounds on polynomial approximations of the discrete logarithm function
Title（参考訳）: 離散対数関数の多項式近似上の境界
Abstract要約: 我々は、離散ログ関数の類似がどの程度うまく近似できるかの有界性を示す、Cupersmith と Shparlinski の古典的な結果を再考する。すべての$D$に対して、上の上限を$(1+o(1)) cdot sqrt2 D p.$$に改善する。また、[CS00] 境界を mathbbF_p2$ の $(x, dlog(x)) の形の点数で改善する。
参考スコア（独自算出の注目度）: 0.749377967268953
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
Abstract: We revisit a classical result of Coppersmith and Shparlinski showing bounds on how well polynomials can approximate the discrete log function. They showed that for any univariate polynomial $f(X) \in \mathbb{F}_p[X]$ with $deg(f) \leq D$, we have: $$ |\{ x \in \mathbb{F}_p^\times \mid f(x) = dlog(x) \}| \leq \sqrt{2 D p}.$$ We show two improvements: (1) For all $D$, we improve the upper bound above to $(1+o(1)) \cdot \sqrt{Dp}$. In particular, we give nontrivial upper bounds on the approximation even for $D > p/2$. This new upper bound is the Johnson bound from the theory of list-decoding of error-correcting codes, and in fact our proof uses a connection to that problem, as well as other combinatorial ideas. (2) For $D = 1$, where both the above bounds are $O(\sqrt{p})$, we give an asymptotically improved upper bound of $O(p^{2/5})$. This is based on the sum-product phenomenon of additive combinatorics. We also improve the [CS00] bounds on the number of points of the form $(x, dlog(x)) \in \mathbb{F}_p^2$ that any bivariate polynomial $Q(X,Y) \in \mathbb{F}_p[X,Y]$ with $deg(Q) \leq D$ can vanish on, with our new bounds approaching the analogue of the Johnson bound for this problem.
Abstract（参考訳）: 我々は、多項式が離散対数関数をいかによく近似できるかの有界性を示す、Cupersmith と Shparlinski の古典的な結果を再考する。彼らは任意の単変数多項式 $f(X) \in \mathbb{F}_p[X]$ with $deg(f) \leq D$ に対して、$$ |\{ x \in \mathbb{F}_p^\times \mid f(x) = dlog(x) \}| \leq \sqrt{2Dp} を持つことを示した。すべての$D$に対して、上記の上限を$(1+o(1)) \cdot \sqrt{Dp}$に改善する。特に、$D > p/2$ であっても近似の非自明な上界を与える。この新たな上限は、ジョンソンが誤り訂正符号のリスト復号理論から有界であり、実のところ、我々の証明は、他の組合せ的アイデアと同様に、その問題と結びついている。 (2)$D = 1$ の場合、上記の境界はともに$O(\sqrt{p})$ であり、漸近的に改善された$O(p^{2/5})$ を与える。これは加法的組合せ論の総和積現象に基づいている。また、ある二変数多項式 $Q(X,Y) \in \mathbb{F}_p[X,Y]$ with $deg(Q) \leq D$ can vanish on という形の点の点数 $(x, dlog(x)) \in \mathbb{F}_p^2$ も改善する。

論文の概要: Bounds on polynomial approximations of the discrete logarithm function

関連論文リスト