論文の概要: Integer Factorization: Another perspective

• arxiv url: http://arxiv.org/abs/2507.07055v1
• Date: Wed, 09 Jul 2025 17:20:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-10 17:37:43.700576
• Title: Integer Factorization: Another perspective
• Title（参考訳）: Integer Factorization:別の視点
• Authors: Gilda Rech Bansimba, Regis Freguin Babindamana,
• Abstract要約: 整数分解は数論と計算機科学の基本的な問題です 我々は、この問題を再考する革新的なアプローチを提案し、新たな視点を提供する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Integer factorization is a fundamental problem in algorithmic number theory and computer science. It is considered as a one way or trapdoor function in the (RSA) cryptosystem. To date, from elementary trial division to sophisticated methods like the General Number Field Sieve, no known algorithm can break the problem in polynomial time, while its proved that Shor's algorithm could on a quantum computer. In this paper, we recall some factorization algorithms and then approach the problem under different angles. Firstly, we take the problem from the ring $\displaystyle\left(\mathbb{Z}, \text{+}, \cdot\right)$ to the Lebesgue space $\mathcal{L}^{1}\left(X\right)$ where $X$ can be $\mathbb{Q}$ or any given interval setting. From this first perspective, integer factorization becomes equivalent to finding the perimeter of a rectangle whose area is known. In this case, it is equivalent to either finding bounds of integrals or finding primitives for some given bounds. Secondly, we take the problem from the ring $\displaystyle\left(\mathbb{Z}, \text{+}, \cdot\right) $ to the ring of matrices $\left( M_{2}\text{(}\mathbb{Z}\text{)}, \ \text{+} \ \cdot\right)$ and show that this problem is equivalent to matrix decomposition, and therefore present some possible computing algorithms, particularly using Gr\"obner basis and through matrix diagonalization. Finally, we address the problem depending on algebraic forms of factors and show that this problem is equivalent to finding small roots of a bivariate polynomial through coppersmith's method. The aim of this study is to propose innovative methodological approaches to reformulate this problem, thereby offering new perspectives.
• Abstract（参考訳）: 整数分解はアルゴリズム数理論と計算機科学の基本的な問題である。 これはRSA(RSA)暗号システムにおける1つの方法またはトラップドア機能と見なされている。 これまでの試行錯誤からジェネラル・ナンバーズ・フィールド・シーブ(General Number Field Sieve)のような洗練された方法まで、既知のアルゴリズムは多項式時間で問題を解くことはできないが、ショアのアルゴリズムが量子コンピュータ上で可能であることが証明された。 本稿では,いくつかの因子化アルゴリズムを思い出し,異なる角度で問題にアプローチする。 まず、この問題を環 $\displaystyle \left(\mathbb{Z}, \text{+}, \cdot\right)$ からルベーグ空間 $\mathcal{L}^{1}\left(X\right)$ へ取り込む。 この観点から、整数分解は、面積が知られている矩形周角を見つけることと等価となる。 この場合、積分の有界点を見つけるか、与えられた有界点に対する原始点を見つけるかのいずれかに等しい。 次に、環 $ {\displaystyle \left(\mathbb{Z}, \text{+}, \cdot\right)$ から行列の環 $\left( M_{2}\text{(}\mathbb{Z}\text{)}, \ \text{+} \cdot\right)$ に問題を取り、この問題が行列分解と等価であることを示し、従って Gr\ オブナー基底と行列対角化を通したいくつかの計算アルゴリズムが存在する。 最後に, 代数的因子の形式に依存する問題に対処し, 銅細工法による二変数多項式の小さな根の発見と等価であることを示す。 本研究の目的は,この問題を再構築するための革新的な方法論的アプローチを提案し,新たな視点を提供することである。

関連論文リスト

• Highway to Hull: An Algorithm for Solving the General Matrix Code Equivalence Problem [4.450536872346658]
  本稿では,一般の場合の行列符号等価問題を解く新しいアルゴリズムを提案する。 我々のアルゴリズムは、ナラヤナンのエフェットal.と同じ時間複雑さを達成できるが、空間の複雑さは低い。
  論文  参考訳（メタデータ） (2025-04-01T22:39:31Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Feature Cross Search via Submodular Optimization [58.15569071608769]
  機能工学の基本的な基礎として機能横断探索について研究する。 この問題に対して単純なgreedy $(1-1/e)$-approximationアルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2021-07-05T16:58:31Z)
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization [49.090785356633695]
  非対称な低ランク分解問題: [mathbbRm min d , mathbfU$ および MathV$ について検討する。
  論文  参考訳（メタデータ） (2021-06-27T17:25:24Z)
• Unique sparse decomposition of low rank matrices [17.037882881652617]
  低階行列Yin mathbbRrtimes n$ のユニークな分解が見つかる。 我々は、ある$Yin MathRrtimes n$が$Xin mathbbRrtimes n$のスパースワイズ分解であることを示す。
  論文  参考訳（メタデータ） (2021-06-14T20:05:59Z)
• The Fine-Grained Hardness of Sparse Linear Regression [12.83354999540079]
  この問題に対して、より優れたブルートフォースアルゴリズムは存在しないことを示す。 また,予測誤差が測定された場合,より優れたブラトフォースアルゴリズムが不可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-06T14:19:43Z)

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

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