素数テスト

-2

可能性の重複：
Fastest primality test 素数テスト

は、誰かが数の素数を決定するための効率的なアルゴリズムを与えることができますか？

大量の素数をテストする場合、従来の反復方法には時間がかかるようです。私はいくつかの確率論的アルゴリズムを試みたが、精度によっては満足しなかった。

2011-11-15 Vijeenrosh P.W

私が知る限り、素数性テストを使うときは、精度と効率の間には常にトレードオフがあります。私は[Miller Rabin primality test]（http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test）のみを使用していますが、あなたがしていることをより正確にしなければならないと思います。 – Lucas

また、十分に大きなkを選んでください。 2^-k（またはn> 1の任意のn^-k）は、指数関数的に速く（読み取り：非常に高速）になります。 –

うわー、それより多くの重複があります - 素数性テストを検索するだけです。 – Cascabel

最も効率的な確率的素数検定は、Rabin-Miller primality test（implementation in C）です。これがRSAが使用するものです。

スピードが必要な場合は確定性テストが難しく、実際のアプリケーションではあまり役に立ちません。

出典

2011-11-15 18:34:06 Dennis

答えて

関連する問題