大きな数値が素数であるか合成であるかを決定的に確認していますか？

Question

私は、小数（10 のような）の小数検査のアルゴリズムを探しています。 良いアルゴリズムはありますか？

理想的には、私はprobabalisticではないアルゴリズムを好むでしょう。

注：数字は50以上200桁未満です。

Answer 1

確率的ではないテストをお探しの場合は、おおよそO（ログ n）の時間で実行されるAKS primality testing algorithmをチェックしてください。あなたの桁数は、これはおそらく実現可能です。

つまり、probabalistic primalityテストは非常に優れており、多くの場合、指数関数的に小さなエラーレートがあります。正当な理由がない限り、そのうちの1つを使用することをお勧めします。

EDIT：私はちょうどthis page containing several C++ implementations of AKSを見つけました。私は彼らが正しく動作するかどうか分からないが、彼らは良い出発点かもしれない。

希望すると便利です。

Answer 2

通常、可能性が高いプライムテストを使用します。私はBPSWをお勧めします。FrobeniusテストやランダムベースのMiller-Rabinテストを続けることができます。いくつかの校正実装を実行するよりも、確かに速く、間違いなくとなるでしょう。

あなたはそれが十分ではないと言います。次に、実際にECPPを使用して証明書を取得します。合理的な実装はPrimoまたはecpp-djです。これらは、1秒未満で200桁の数字の素数性を証明し、独自に検証できる証明書を返すことができます。

APR-CLです。欠点は、実装を信頼するために証明書を返さないことです。実装が正しければ決定論的に正しい "はい"または "いいえ"の出力が得られます。 Pari/GPはisprimeコマンドでAPR-CLを使用し、David Cleaverは優れたオープンソース実装を持っています：mpz_aprcl。これらの実装では、さまざまなソフトウェアでコードのレビューと日々の使用が行われています。

AKSは実際には恐ろしい方法です。 完全には、証明方法を使用している点と、可能性が高い可能性が高い主なテストを最初から守っていない証明書を返しません。それはまた恐ろしく遅いです。 200桁の数字は、私が知っている実装の実用的なポイントをはるかに超えています。前述のecpp-djソフトウェアには「高速」なソフトウェアが含まれているので、試してみることができます。他にもいくつかの実装があります。

スピードの考え方については、いくつかの実装の時があります。私は、AKS、APR-CL、またはBPSWの実装が、表示されているものより速いことは知らない（あなたが知っていればコメントしてください）。 Primoはecpp-djよりも少し遅く始まりますが、500桁以上になると早くなり、より良いスロープが得られます。それは大きな入力（2,000-30,000桁）のための選択のプログラムです。