論文の概要: Decomposition of RSA modulus applying even order elliptic curves

• arxiv url: http://arxiv.org/abs/2503.00950v1
• Date: Sun, 02 Mar 2025 16:09:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-05 19:12:39.916572
• Title: Decomposition of RSA modulus applying even order elliptic curves
• Title（参考訳）: 偶数次楕円曲線を適用したRSA率の分解
• Authors: Jacek Pomykała, Mariusz Jurkiewicz,
• Abstract要約: 効率的な整数分解アルゴリズムはRSA暗号スキームのすべての変種をゼロにする。 滑らか性に対する一般化されたアプローチの自然な拡張と2ドル進点順序の分離が組み合わさって、ファクタリングアルゴリズムを提案することを実証する。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: An efficient integer factorization algorithm would reduce the security of all variants of the RSA cryptographic scheme to zero. Despite the passage of years, no method for efficiently factoring large semiprime numbers in a classical computational model has been discovered. In this paper, we demonstrate how a natural extension of the generalized approach to smoothness, combined with the separation of $2$-adic point orders, leads us to propose a factoring algorithm that finds (conjecturally) the prime decomposition $N = pq$ in subexponential time $L(\sqrt 2+o(1), \min(p,q))$. This approach motivated by the papers \cite{Len}, \cite{MMV} and \cite{PoZo} is based on a more careful investigation of pairs $(E,Q)$, where $Q$ is a point on an elliptic curve $E$ over $\Z _N$. Specifically, in contrast to the familiar condition that the largest prime divisor $P^+(\ord Q_p)$ of the reduced order $\ord Q_p$ does not divide $\#E(\F_q)$ we focus on the relation between $P^+(\ord Q_r)$ and the smallest prime number $l_{\min}(E,Q)$ separating the orders $\ord Q_p$ and $\ord Q_q$. We focus on the ${\calE}_2$ family of even order elliptic curves over $\Z_N$ since then the condition $l_{\min}(E,Q)\le 2$ holds true for large fraction of points $(x,y)\in E(\Z_N)$. Moreover if we know the pair $(E,Q)$ such that $P^+(\ord Q_r)\le t<l_{\min}(E,Q)$ and $d=\max_{r\in \{p,q\}}(\ord Q_r)$ is large in comparison to $\min_{r\in \{p,q\}}|a_r(E)|\neq 0$ then we can decompose $N$ in deterministic time $t^{1+o(1)}$ by representing $N$ in base $d$.
• Abstract（参考訳）: 効率的な整数分解アルゴリズムはRSA暗号スキームのすべての変種をゼロにする。 長い年月を経たにもかかわらず、古典的な計算モデルにおいて大きな半素数を効率的に分解する方法は発見されていない。 本稿では,滑らか性に対する一般化されたアプローチの自然な拡張と2ドル進点順序の分離が組み合わさって,素分解 $N = pq$ in subexponential time $L(\sqrt 2+o(1), \min(p,q))$ を求める分解アルゴリズムを提案する。 このアプローチは、論文 \cite{Len}, \cite{MMV} と \cite{PoZo} によって動機付けられたもので、ペアの $(E, Q)$ をより慎重に調べることに基づいている。 具体的には、縮小順序の最大の素因子 $P^+(\ord Q_p)$ が$\ord Q_p$ を分割しないというよく知られた条件とは対照的に、$P^+(\ord Q_r)$ と最小素数 $l_{\min}(E,Q)$ は$\ord Q_p$ と $\ord Q_q$ を分離する。 任意の順序楕円曲線が$\Z_N$を超えるような${\calE}_2$ファミリに焦点をあて、それ以来、条件 $l_{\min}(E,Q)\le 2$ は、大小の点 $(x,y)\in E(\Z_N)$ に対して真である。 さらに、$P^+(\ord Q_r)\le t<l_{\min}(E,Q)$ と $d=\max_{r\in \{p,q\}}(\ord Q_r)$ が $\min_{r\in \{p,q\}}|a_r(E)|\neq 0$ であるようなペア $(E,Q)$ を知っていれば、$N$ を決定論的時間 $t^{1+o(1) で分解することができる。

関連論文リスト

• On estimating the trace of quantum state powers [2.637436382971936]
  量子状態のトレースを推定する計算複雑性を、$n$-qubit混合量子状態$rho$に対して$texttr(rhoq)$で調べる。 我々の高速化は、正のパワー関数の計算可能な一様近似を量子特異値変換に効率よく導入することで達成される。
  論文  参考訳（メタデータ） (2024-10-17T13:57:13Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
  量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
  論文  参考訳（メタデータ） (2023-02-20T19:11:44Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes [12.640283469603357]
  正規化定数の計算における計算複雑性について検討する。 例えば、$sum_Sdet(bf A_S,S)p$は、すべての(固定された)正の偶数に対して、$p$ が UP-hard で Mod$_3$P-hard であることを示す。
  論文  参考訳（メタデータ） (2021-11-28T14:08:25Z)
• Simplest non-additive measures of quantum resources [77.34726150561087]
  我々は $cal E(rhootimes N) = E(e;N) ne Ne$ で説明できる測度について研究する。
  論文  参考訳（メタデータ） (2021-06-23T20:27:04Z)
• The planted matching problem: Sharp threshold and infinite-order phase transition [25.41713098167692]
  ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。 任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
  論文  参考訳（メタデータ） (2021-03-17T00:59:33Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。