論文の概要: From Worst to Average Case to Incremental Search Bounds of the Strong Lucas Test
- arxiv url: http://arxiv.org/abs/2406.04718v1
- Date: Fri, 7 Jun 2024 07:58:13 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-10 14:59:58.610561
- Title: From Worst to Average Case to Incremental Search Bounds of the Strong Lucas Test
- Title（参考訳）: ストロングルーカス試験における平均値からインクリメンタルサーチバウンドへ
- Authors: Semira Einsele, Gerhard Wunder,
- Abstract要約: 強力なルーカステストは暗号ライブラリで広く使われている確率的原始性テストである。
素数検定では、最悪の場合の誤差確率は、合成物を素数として誤って特定する可能性の上限として機能する。
本稿では, 整数が$t$連続試験ラウンドをパスし, 計算コストの低い追加の標準テストとともに, 実際に素数であることを示すことによって, ギャップを解消する。
- 参考スコア（独自算出の注目度）: 1.4732811715354452
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The strong Lucas test is a widely used probabilistic primality test in cryptographic libraries. When combined with the Miller-Rabin primality test, it forms the Baillie-PSW primality test, known for its absence of false positives, undermining the relevance of a complete understanding of the strong Lucas test. In primality testing, the worst-case error probability serves as an upper bound on the likelihood of incorrectly identifying a composite as prime. For the strong Lucas test, this bound is $4/15$ for odd composites, not products of twin primes. On the other hand, the average-case error probability indicates the probability that a randomly chosen integer is inaccurately classified as prime by the test. This bound is especially important for practical applications, where we test primes that are randomly generated and not generated by an adversary. The error probability of $4/15$ does not directly carry over due to the scarcity of primes, and whether this estimate holds has not yet been established in the literature. This paper addresses this gap by demonstrating that an integer passing $t$ consecutive test rounds, alongside additional standard tests of low computational cost, is indeed prime with a probability greater than $1-(4/15)^t$ for all $t\geq 1$. Furthermore, we introduce error bounds for the incremental search algorithm based on the strong Lucas test, as there are no established bounds up to date as well. Rather than independent selection, in this approach, the candidate is chosen uniformly at random, with subsequent candidates determined by incrementally adding 2. This modification reduces the need for random bits and enhances the efficiency of trial division computation further.
- Abstract（参考訳）: 強力なルーカステストは暗号ライブラリで広く使われている確率的原始性テストである。
ミラー・ラビン素性テストと組み合わせると、バイリー・PSW素性テスト(英語版)(Baillie-PSW primality test)を形成し、偽陽性が欠如していることで知られ、強いルーカステストの完全な理解の妥当性を損なう。
素数検定では、最悪の場合の誤差確率は、合成物を素数として誤って特定する可能性の上限として機能する。
強いルーカス試験では、この境界は奇数合成に対して4/15ドルであり、双子素数の積ではない。
一方、平均ケース誤差確率は、ランダムに選択された整数がテストによって素数として不正確に分類される確率を示す。
この境界は実践的な応用において特に重要であり、敵によってランダムに生成され、生成されない素数をテストする。
4/15$の誤差確率は、素数の不足と、この推定値がまだ文献で確立されていないため、直接引き継がれていない。
このギャップは、整数が$t$連続テストラウンドをパスし、計算コストの低い追加の標準テストとともに、すべての$t\geq 1$に対して1-(4/15)^t$以上の確率で実際に素であることを示すことで解決される。
さらに,Lasテストに基づくインクリメンタル検索アルゴリズムの誤差境界を導入する。
独立選択ではなく、このアプローチでは、候補はランダムに一様選択され、その後の候補は2を漸進的に加えることで決定される。
この修正はランダムビットの必要性を減らし、試行分割計算の効率をさらに高める。
関連論文リスト
- Permutation tests for quantum state identity [0.0]
n$未知の量子状態が等しいか不等であるかを決定する問題は、量子状態アイデンティティ問題として知られている。
置換テストはこのタスクに最適であることが知られており、2つの入力状態に対してはよく知られたスワップテストと一致する。
この研究は、量子状態のアイデンティティ問題(きめ細かい定式化)の基盤となる構造を捉えようとする。
論文 参考訳（メタデータ） (2024-05-15T18:00:07Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - Precise Error Rates for Computationally Efficient Testing [75.63895690909241]
本稿では,計算複雑性に着目した単純な対数-単純仮説テストの問題を再考する。
線形スペクトル統計に基づく既存の試験は、I型とII型の誤差率の間の最良のトレードオフ曲線を達成する。
論文 参考訳（メタデータ） (2023-11-01T04:41:16Z) - Anytime-valid t-tests and confidence sequences for Gaussian means with unknown variance [30.14855064043107]
1976年、レイは未知の分散を持つガウス分布の平均$mu$に対して非自明な自信列を構築した。
ここでは、一般化された非可積分なマルティンガレと拡張されたヴィルの不等式を用いる彼の構成の詳細について詳しく述べる。
我々は、同じ設定で2つの新しいE-プロセスと信頼性シーケンスを開発する。
論文 参考訳（メタデータ） (2023-10-05T17:43:26Z) - SPRT-based Efficient Best Arm Identification in Stochastic Bandits [31.359578768463752]
本稿では,固定信頼度設定におけるマルチアームバンディットの腕識別問題について検討する。
バンドイットの指数族に対する既存のアルゴリズムは計算上の課題に直面している。
逐次テストに有効であることが知られている確率比ベースのテストを採用するフレームワークが提案されている。
論文 参考訳（メタデータ） (2022-07-22T15:54:53Z) - Exact Paired-Permutation Testing for Structured Test Statistics [67.71280539312536]
構造化されたテスト統計群のペア置換テストに対して,効率的な正確なアルゴリズムを提案する。
我々の正確なアルゴリズムはモンテカルロ近似よりも10ドル速く、共通のデータセットに20000ドルのサンプルがある。
論文 参考訳（メタデータ） (2022-05-03T11:00:59Z) - Group Testing with Non-identical Infection Probabilities [59.96266198512243]
そこで我々は,集合形成法を用いた適応型グループテストアルゴリズムを開発した。
提案アルゴリズムは, エントロピー下界に近い性能を示す。
論文 参考訳（メタデータ） (2021-08-27T17:53:25Z) - Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm
for Stochastic Bandits with Corruptions [91.8283876874947]
我々は,T段の固定予算設定において,敵対的腐敗を伴う連続的包帯に対する最適な腕識別(BAI)問題を考察した。
我々は, 汚職の量に依存しない新しいランダム化アルゴリズム, Probabilistic Shrinking($u$) (PSS($u$)) を設計する。
CPS が十分に大きいとき、BAI 確率を$Trightarrow infty$ として達成できるアルゴリズムは存在しない。
論文 参考訳（メタデータ） (2020-10-15T17:34:26Z) - Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。
一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-09-14T16:09:17Z) - A New Randomized Primal-Dual Algorithm for Convex Optimization with
Optimal Last Iterate Rates [16.54912614895861]
我々は,非滑らかな制約付き凸最適化問題のクラスを解くために,新しいランダム化ブロック座標原始双対アルゴリズムを開発した。
我々は,一般凸性と強い凸性という2つのケースにおいて,アルゴリズムが最適収束率を達成することを証明した。
その結果,提案手法は異なる実験における性能向上に寄与していることがわかった。
論文 参考訳（メタデータ） (2020-03-03T03:59:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。