Miller-Rabin 検定が 10¹⁸ までのすべての数について正しくなるには、どの証人のセットがあれば十分ですか? n < 341550071728321 の場合、証人として 17 までの素数を使用すれば十分であることを私は知っています。
3 に答える
2
このレコード ページによると、7 つの SPRP ベースのセットは{2, 325, 9375, 28178, 450775, 9780504, 1795265022}、少なくともn = 2^64 ( > 10^19).
于 2014-03-05T10:56:22.290 に答える
0
OEISによると、3825123056546413051 までの数に対しては、23 までの証人の使用で十分です。
于 2014-03-05T10:00:02.690 に答える
0
Miller-Rabin 検定の代わりに Baillie-Wagstaff 検定を使用する場合は、2^64 までの素数を分類する際にエラーがないことが証明されています。コーディングはそれほど複雑ではなく、関数は Miller-Rabin テストよりも高速に実行され、既知の分類エラーはありません。
于 2014-03-05T13:33:53.163 に答える