Fugu-MT 論文翻訳(概要): Computing $\varphi(N)$ for an RSA module with a single quantum query

論文の概要: Computing $\varphi(N)$ for an RSA module with a single quantum query

arxiv url: http://arxiv.org/abs/2406.04061v1
Date: Thu, 6 Jun 2024 13:30:18 GMT
ステータス: 処理完了
システム内更新日: 2024-06-07 14:49:58.810145
Title: Computing $\varphi(N)$ for an RSA module with a single quantum query
Title（参考訳）: 単一の量子クエリを持つRSAモジュールに対する$\varphi(N)$の計算
Authors: Luis Víctor Dieulefait, Jorge Urróz,
Abstract要約: RSAモジュールの$N$に対して$varphi(N)$を、ランダムに選択された整数の代入として$N$を演算する計算時間アルゴリズムを与える。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In this paper we give a polynomial time algorithm to compute $\varphi(N)$ for an RSA module $N$ using as input the order modulo $N$ of a randomly chosen integer. The algorithm consists only on a computation of a greatest common divisor, two multiplications and a division. The algorithm works with a probability of at least $1-\frac{C\log\log N}{N^{1/2}}$.
Abstract（参考訳）: 本稿では RSA モジュール $N$ に対して、ランダムに選択された整数の順序変調 $N$ を入力として、多項式時間アルゴリズムで $\varphi(N)$ を計算する。このアルゴリズムは、最大公約数の計算、2つの乗算、1つの除算のみで構成されている。このアルゴリズムは、少なくとも1-\frac{C\log\log N}{N^{1/2}}$の確率で動作する。

関連論文リスト

Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
論文参考訳（メタデータ） (2024-08-10T04:26:19Z)
Low-Complexity Integer Divider Architecture for Homomorphic Encryption [5.857929080874288]
ホモモルフィック暗号化(HE)は、計算を直接暗号文で行うことができ、プライバシ保護のクラウドコンピューティングを可能にする。余剰かつ活発な数学的証明を計算するアルゴリズムが提案されている。
論文参考訳（メタデータ） (2024-01-19T23:53:59Z)
Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。目標は、低ランク因子の積として$mathbfA$を近似することである。我々の手法はBMF問題の他の一般的な変種に一般化する。
論文参考訳（メタデータ） (2023-06-02T18:55:27Z)
Most Neural Networks Are Almost Learnable [52.40331776572531]
固定された$epsilon>0$とdeep $i$に対して、深さ$i$のランダムなXavierネットワークを学習するポリ時間アルゴリズムが存在することを示す。このアルゴリズムは時間とサンプルの複雑さが$(bard)mathrmpoly(epsilon-1)$であり、$bar d$はネットワークのサイズである。シグモイドやReLU様の活性化の場合、境界は$(bard)mathrmpolylog(eps)に改善できる。
論文参考訳（メタデータ） (2023-05-25T22:27:42Z)
Distributed Shor's algorithm [1.7396274240172125]
ショアのアルゴリズムはピーター・ショアが提唱した最も重要な量子アルゴリズムの1つである。 2つの量子コンピュータを別々に使い、$dfracsr$を$sin0, 1, cdots, r-1$と見積もる。複数の制御量子ビットを使用する従来のショアのアルゴリズムと比較して、我々のアルゴリズムは、約$dfracL2$ qubitsを減らし、各コンピュータの回路深さを減らしている。
論文参考訳（メタデータ） (2022-07-13T06:00:03Z)
Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文参考訳（メタデータ） (2022-04-13T22:18:47Z)
TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。本稿では,この数値をほぼ最適に推定する手法を提案する。
論文参考訳（メタデータ） (2022-02-15T03:49:28Z)
Pseudo Polynomial-Time Top-k Algorithms for d-DNNF Circuits [0.0]
我々は,最大値w.r.$$$の内,$C$のモデルを計算するアルゴリズムを提案する。また、d-DNNF回路に$C$を変換する擬似時間アルゴリズムを、上位の$k$に値を持つ$C$のモデルによって正確に満たされる。
論文参考訳（メタデータ） (2022-02-11T23:53:43Z)
A quantum algorithm for computing the Carmichael function [0.0]
量子コンピュータは、多くの数理論問題を効率的に解くことができる。本稿では,任意の整数$N$に対して,所望の 1 に近い確率でカーマイケル関数を計算するアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-11-03T19:30:27Z)
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)
Quantum algorithms for the Goldreich-Levin learning problem [3.8849433921565284]
Goldreich-Levinアルゴリズムは元々暗号目的のために提案され、その後学習に適用された。ウォルシュ係数を持つベクトルを$w$で出力するには$poly(n,frac1epsilonlogfrac1delta)$時間を要する。本稿では,この問題に対する量子アルゴリズムをクエリ複雑性$O(fraclogfrac1deltaepsilon4)$で与えられる。
論文参考訳（メタデータ） (2019-12-31T14:52:36Z)

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