ミラーラビン素数検査は2種類ですか？

突然、私は2種類のミラーラビン素数検査法に遭遇しました。 uses randomsとdoes not use randomsです。ミラーラビン素数検査は2種類ですか？

2つ目の内部に隠れたランダムな世代がありますか？ありがとうございました。

2016-12-08 Isura Manchanayake

ありがとうございました。確率的アルゴリズムがはるかに高速であり、なぜ決定論的アルゴリズムがあまり普及していないのかを理解することができます。 –

決定的なM-Rテストは、人々がそれについて知らないために、あまり一般的ではありません。特に最適なセットを使用すると、すべての64ビット入力に対して非常に効率的な決定論的回答が得られ、このサイズの確率的テストを使用して信頼性の高い結果を得るために必要なテストが少なくなります。したがって実際にはより速いです（正しい結果を気にしない限り）。 – DanaJ

はい。ここでは、決定論的MRと平方根境界法を比較するための一種の研究を行った。ここではhttps://isuramanchanayake.wordpress.com/2016/12/08/algorithms/#graphical-comparison。そこでは、あなたが言っているように、10以下の値ではあまり効率的ではないとして、大きな入力に対してdet-MRがはるかに優れていることがわかりました^ 12 –

第2のものは、Miller-Rabin素数性試験のdeterministic variantである。代わりに、乱数から生成された「証人」番号を使用する、十分であることが知られている素数のリストが代わりに使用される：数nが試験される

すべて< 2（LN nをしようとし、小さいです）2は必要ではない。潜在的な目撃者のより小さいセットが十分であることがわかっているので、

n < 3,825,123,056,546,413,051の場合、a = 2,3,5,7,11,13,17,19,11および23.

これはalistの連結されたソースコード内の素数のリストです。

出典

2016-12-08 21:25:31 samgak

ありがとう –

ミラーラビン素数検査は2種類ですか？

答えて

関連する問題