大きな（10 200のような）数を素数性テストするアルゴリズムを探しています。良いアルゴリズムはありますか？
理想的には、確率論的ではないアルゴリズムを好みます。
注：数字は50桁以上200桁未満です。
1467 次
2 に答える
12
非確率的テストを探している場合は、およそO（log 6 n）時間で実行されるAKS素数テストアルゴリズムを確認することをお勧めします。あなたが持っている桁数については、これはおそらく実行可能です。
とはいえ、確率的素数性テストは非常に優れており、多くの場合、エラー率は指数関数的に小さくなります。正当な理由がない限り、これらのいずれかを使用することをお勧めします。
編集：AKSのいくつかのC++実装を含むこのページを見つけました。それらが正しく機能するかどうかはわかりませんが、良い出発点になるかもしれません。
お役に立てれば！
于 2012-02-05T19:57:57.780 に答える
6
通常、確率的素数テストを使用します。BPSWをお勧めします。これは、より確実性が必要な場合は、フロベニウス検定および/またはランダムベースのミラーラビン検定で追跡できます。これは、いくつかの証明実装を実行するよりも高速で、間違いなく確実です。
それだけでは不十分だとあなたが言ったとしましょう。次に、本当にECPPを使用して、証明書を取得します。合理的な実装はPrimoまたはecpp-djです。これらは、1秒未満で200桁の数字の素数性を証明し、独立して検証できる証明書を返すことができます。
APR-CLはもう1つの合理的な方法です。欠点は、証明書を返さないため、実装を信頼していることです。実装が正しければ、決定論的に正しい「yes」または「no」の出力が得られます。Pari / GPはそのisprimeコマンドでAPR-CLを使用し、DavidCleaverには優れたオープンソース実装mpz_aprclがあります。これらの実装には、コードレビューがあり、さまざまなソフトウェアで毎日使用されているので、良いはずです。
AKSは、実際に使用するのは恐ろしい方法です。証明書は返されません。また、壊れた実装を見つけるのはそれほど難しくありません。これは、そもそも証明方法と確率的素数テストを使用するという点を完全に打ち負かします。それもひどく遅いです。200桁の数字は、私が知っている実装の実用的なポイントをはるかに超えています。前述のecpp-djソフトウェアには「高速」なものが含まれているので、試してみることができます。他にもかなりの数の実装があります。
速度のいくつかのアイデアのために、ここにいくつかの実装の時があります。示されているものよりも高速なAKS、APR-CL、またはBPSWの実装を知りません（知っている場合はコメントしてください）。Primoは、示されているecpp-djよりも少し遅く開始しますが、500桁程度の場合は高速であり、それを超えるとより良い勾配になります。これは、大きな入力（2,000〜30,000桁）に最適なプログラムです。
于 2015-07-14T05:56:40.823 に答える