論文の概要: An Algebraic-Geometry Approach to Prime Factorization
- arxiv url: http://arxiv.org/abs/2209.11650v1
- Date: Fri, 23 Sep 2022 15:31:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-25 10:17:24.388073
- Title: An Algebraic-Geometry Approach to Prime Factorization
- Title（参考訳）: 代数幾何学による素因数分解
- Authors: Alberto Montina, Stefan Wolf
- Abstract要約: 素因数分解のための新しいアルゴリズムは、暗号アルゴリズムの現在の実装に実践的な影響を与える可能性がある。
n/2以上のパラメータを効率的に評価できる多様体が存在することを示す。
ある場合、 n/2 以上のパラメータが与えられたとき、効率的に点を評価できる多様体が存在することを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: New algorithms for prime factorization that outperform the existing ones or
take advantage of particular properties of the prime factors can have a
practical impact on present implementations of cryptographic algorithms that
rely on the complexity of factorization. Currently used keys are chosen on the
basis of the present algorithmic knowledge and, thus, can potentially be
subject to future breaches. For this reason, it is worth to investigate new
approaches which have the potentiality of giving a computational advantage. The
problem has also relevance in quantum computation, as an efficient quantum
algorithm for prime factorization already exists. Thus, better classical
asymptotic complexity can provide a better understanding of the advantages
offered by quantum computers. In this paper, we reduce the factorization
problem to the search of points of parametrizable varieties, in particular
curves, over finite fields. The varieties are required to have an arbitrarily
large number of intersection points with some hypersurface over the base field.
For a subexponential or poly- nomial factoring complexity, the number of
parameters have to scale sublinearly in the space dimension n and the
complexity of computing a point given the parameters has to be subexponential
or polynomial, respectively. We outline a procedure for building these
varieties, which is illustrated with two constructions. In one case, we show
that there are varieties whose points can be evaluated efficiently given a
number of parameters not greater than n/2. In the other case, the bound is
dropped to n/3. Incidentally, the first construction resembles a kind of
retro-causal model. Retro-causality is considered one possible explanation of
quantum weirdness.
- Abstract（参考訳）: 素因数分解のための新しいアルゴリズムは、既存のものよりも優れており、素数分解の複雑さに依存する暗号アルゴリズムの現在の実装に実際的な影響を与えうる。
現在使われているキーは、現在のアルゴリズムの知識に基づいて選択され、将来の侵害の可能性がある。
このため、計算上の優位性を与える可能性を持つ新しいアプローチを検討すべきである。
この問題は、素因数分解のための効率的な量子アルゴリズムがすでに存在するため、量子計算にも関係がある。
したがって、古典的漸近的複雑性は量子コンピュータが提供する利点をよりよく理解することができる。
本稿では、有限体上のパラメトリザブル多様体(特に曲線)の点の探索による分解問題を小さくする。
これらの多様体は、基底体上の超曲面を持つ任意の数の交点を持つ必要がある。
部分指数あるいは多項因数分解複雑性の場合、パラメータの数は空間次元 n において線型にスケールし、パラメータが与えられた点をそれぞれ部分指数あるいは多項式で計算しなければならない。
2つの構成図で示されるこれらの多様体の構築手順について概説する。
ある場合、 n/2 以上のパラメータが与えられたとき、効率的に点を評価できる多様体が存在することを示す。
もう一方の場合、境界は n/3 に下げられる。
ちなみに、最初の構造はレトロコーサルモデルに似ている。
Retro-Causalityは、量子の奇妙な説明の1つと考えられている。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Quantum and Classical Combinatorial Optimizations Applied to
Lattice-Based Factorization [0.046040036610482664]
格子ベースのファクタリングは、より大きな数にうまくスケールしないことが示される。
我々は、CVPの特定の事例と、分解パイプラインの他の部分に量子技術を適用する機会について検討する。
論文 参考訳（メタデータ） (2023-08-15T14:31:25Z) - Integer Factorisation, Fermat & Machine Learning on a Classical Computer [0.0]
我々は、整数因数分解問題を二項分類問題に還元するために、ローレンスのフェルマー因数分解アルゴリズムの拡張を利用する。
大規模な擬似ランダム素数の生成が容易な分類問題に対処するため、必要に応じて大規模なトレーニングデータのコーパスを合成的に生成する。
論文 参考訳（メタデータ） (2023-07-16T22:39:00Z) - Shallow Depth Factoring Based on Quantum Feasibility Labeling and
Variational Quantum Search [0.0]
整数分解は、特に量子コンピューティングの文脈において顕著な研究課題である。
本稿では,新しい量子アルゴリズムShallow Depth Factoring (SDF)を提案する。
論文 参考訳（メタデータ） (2023-05-31T04:18:04Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - An efficient quantum algorithm for lattice problems achieving
subexponential approximation factor [2.3351527694849574]
整数格子のクラスに対する指数近似係数を用いて,境界距離復号法(BDD)問題を解く量子アルゴリズムを提案する。
量子アルゴリズムの実行時間は、近似因子の1つの範囲と、第2の範囲の近似因子のサブ指数時間である。
この見解は、有限アーベル群の観点からクリーンな量子アルゴリズムを定め、格子理論から相対的にほとんど使用せず、次元以外のパラメータの格子問題に対する近似アルゴリズムを探求することを提案している。
論文 参考訳（メタデータ） (2022-01-31T18:58:33Z) - Using Shor's algorithm on near term Quantum computers: a reduced version [0.0]
我々は、ノイズの多い量子デバイス上で分解可能な数値の範囲を拡大するステップを推し進めるShorのアルゴリズムの縮小版を導入する。
特に、ほとんどのケースで注目すべき結果が得られており、しばしば提案されたアルゴリズムの1つで与えられた数を分解できる。
論文 参考訳（メタデータ） (2021-12-23T15:36:59Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。
これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
論文 参考訳（メタデータ） (2020-11-09T01:13:07Z) - Refined bounds for algorithm configuration: The knife-edge of dual class
approximability [94.83809668933021]
トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。
この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。
我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
論文 参考訳（メタデータ） (2020-06-21T15:32:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。