第1部 全3回：基本テスト

注）全ての式において、nは植生を検査する数値である。

1. 1 室内テスト。2から床まで(n{displaystyle{sqrt{n}}})を各素数で割った値。
2. 2 フェルマーの小定理。警告: a のすべての値に対してであっても、誤検出が起こる可能性があります。2≦A≦n-1となるようなaの整数値を選んでください。 an (mod n) = a (mod n) であれば、nはおそらく素数です。これが成立しない場合、nは素数ではありません。素数の信頼性を高めるために、aの値を変えて繰り返す

3. 3 Miller-Rabinテスト。警告: a の値が複数ある場合、誤検出となることがありますが、ほとんどありません。n-1=2 sec∗d{displaystyle n-1=2^{s}*d} となるようなsとdの値を求めよ。2≦1≦n-1となるような整数値を選び、ad＝＋1（mod n）または-1（mod n）であれば、nは素数であると考えられる。テスト結果へスキップします。そうでない場合は、次のステップに進んでください。答えを2乗する（a2d{displaystyle a^{2d}）。もしこれが-1（mod n）に等しければ、nはおそらく素数である。テスト結果へスキップします。それ以外の場合は、a2s-1dまで(a4d{displaystyle a^{4d}, etc)を繰り返します。もし、±1{}でない数（mod n）を2乗して、+1（mod n）で終わったら、nは素数ではありません。a2s-1d≠±1{displaystyle a^{2^{s-1}d}neq}pm 1} (mod n) ならば、nは素数でないことになります。テスト結果: nがテストに合格した場合、信頼性を高めるために異なる値のaで繰り返す。

第2部 第3部 基礎テストの理解

1. 1 試行錯誤の方法を理解する。素数の定義によると、nは2以上の平均的な整数で割り切れない場合にのみ素数となる。この式は、不要なテストを削除することで時間を節約します（例えば、3のテストの後、9のテストは必要ありません）。Floor (x) は x を最も近い整数 ≤ x に丸める。
2. 2 modulo演算を理解する。x mod y」（モジュロの略）は、「xをyで割って余りを求める」という意味である。" をゼロに戻す。多くの電卓にはmodボタンがありますが、大きな数を手動で解く方法については、この章の最後をご覧ください。

3. フェルマーの小定理の落とし穴は知っている。このテストに失敗した数はすべて合成数（非素数）ですが、残念ながらこのテストに合格した数は素数の可能性が高いだけなのです。誤検出を確実に防ぎたい場合は、「カーマイケル数」（このテストに毎回合格する）と「フェルマー擬似素数」（aのある値に対してのみ合格する）のリストからnを探します。

4. 4 可能な限り Miller-Rabin テストを使用する。手動でテストするのは面倒だが、このテストはソフトウェアでよく使われる。これは現実的な速度で行うことができ、Fermatの方法よりも誤認識が少ない。合成数対Aの値のうち、1/4以上は誤検出をしない。Aの値をいくつかランダムに選び、それらがすべてこのテストに合格すれば、nが素数であることをかなり確信できる。

5. 5 大きな数に対してモジュロ演算を行うことができる。modのついた電卓が使えない場合や、電卓がそこまで数字を表示できない場合は、指数の性質やモジュロ演算を使って簡略化しましょう。350{displaystyle 3^{50}mod 50}の例： (325)∗325){displaystyle(3^{25}*3^{25})mod 50. 手計算の場合はさらに細分化が必要かもしれません)(325∗325{displaystyle (3^{25}*3^{25}) mod 50 = (325{displaystyle (3^{25}) mod 50∗325{displaystyle*3{25} mod 50) mod 50. これはmodulo multiplicationの性質です)325{displaystyle 3^{25}mod 50=43. (325{displaystyle(3^{25}}mod 50∗325{displaystyle*3^{25}mod 50) mod 50=(43∗43){displaystyle(43*43)}} となる。mod 50=1849{displaystyle=1849}mod 50=49{displaystyle=49}

第3部3: 中国残留定理テスト

1. 1 2つの数字を選んでください。片方の数字は素数ではなく、もう片方の数字は素数を調べる必要がある数字です。「Prime1=35Prime2=97。

2. 2 ゼロより大きく、素数1と素数2より小さい2つのデータ点をそれぞれ選択する。これらは互いに等しくない。

3. 3 素数1と素数のMMI（数学的乗法逆数）を計算する：MMI=(素2^(素1-2))%PRIMEMI2=(素1^(素2-2))%2E. gMMI1=(97^33)%35MMI2=(35^95)%97.

4. 4 モジュールのLog2までの各MMIについてバイナリテーブルを作成する。 for MMI1F(1)=Prime2%Prime1=97%35=27F(2)=F(1)*F(1)%Prime1=27*27%35=29F(4)=F(2)*F(2)%Prime1=29*29%35=1F(8)=F(4)*F(4)%Prime1=1*1%35=1F(16)=F(8)*Binary number of Prime1-235-2=33(10001) Base 2MMI1=F(33)=F(32)*F(1)mod 35MMI1=F(33)=1*27 mod 35MMI1=27mmi2f(1)=MMI1Prime1%Prime2=35%97=35F(2)=F(1)*F(1)%Prime2=35*35 mod 97=61F(4)=F(2)*F(2)%Prime2=61*61 mod 97=35F(8)=mod 97=35F(32)=F(16)*F(16)%Prime2=35*35 mod 97=61F(64)=F(32)*F(32)%Prime2=61*61 mod 97=35F(128)=F(64)*F(64)%Prime2=35*35 mod 97=61 Prime2 の2進数の計算 -297-2=95=(1011111) base2mi2=()（（（（F(64)*F(16)%97)*F(8)*F(4)%97)*97)*35%97)*61%97)*35%97) MMI2=61.

5. 5 計算 (Data1*Prime2*MMI1+Data2*Prime1*MMI2)%(Prime1*Prime2) answer=(1*97*27+2*35*61)%(97*35) answer=(2619+4270)%3395 answer=99。

6. 6 「Prime1」が素数でないことを確認する計算（答え - データ1） %Prime199-1%35 = 28 28 は 0 より大きく、35 は素数ではないため。

7. 7 Prime2がPrimeかどうかをチェックするCalculate (answer - data2) %Prime299-2%97=0 なぜなら0は0に等しく、97は素数である可能性があるからです。

8. 8 手順1～7をあと2回以上繰り返してください。ステップ7が0の場合：別の「素数1」を使用し、素数1は非素数である。別の素数1を使い、素数1が実際の素数である。この場合、ステップ6と7は0になるはずです。データ1とデータ2には、異なるデータポイントを使用します。ステップ7が毎回0であれば、prime2が素数である確率は非常に高くなります。ステップ1から7は、最初の数が非素数で、2番目の素数が非素数「prime1」の因数である場合、場合によっては失敗することが知られています。これは、両方の数字が素数であるすべての場合に適用されます。ステップ1〜7を繰り返す理由は、素数1が素数でなく、素数2が素数でない場合でも、ステップ7では、どちらか一方または両方の数が0になるケースがあるからである。このようなケースは稀です。素数1を素数でない別の数に変更することで、素数2が素数でない場合、手順7で素数2はすぐに0にならなくなります。prime1 "がprime2の因数である場合を除き、ステップ7では常に素数は0に等しくなる。

• 1000以下の168個の素数は、2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 197, 199, 211, 223, 227, 229, 233, 249, 251, 257, 263, 269, 271, 277, 283, 283, 331, 317, 317]です。347,349, 353, 359, 367, 373, 379, 383, 389, 397, 401,409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683,691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839,853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.
• 数が多い場合、テストスプリットはより洗練された方法よりも遅くなりますが、それでも数が少ない場合にはかなり効果的です。大量にある植生検査でも、小さな要因を確認してから、小さな要因が見つからなければ、より高度な手法に切り替えることも少なくない。