フェルマーの素数性テスト - 開発者ドキュメント

1. 序章

素数は何世紀にもわたって数学者の注目を集めてきました。今日、彼らはコンピュータサイエンスと暗号化において重要な役割を果たしています。

数が素数であるかどうかを判断する簡単な方法は、2から。までの数で割り切れるかどうかを確認することです。ただし、このブルートフォース方式は計算効率が高くありません。

エラトステネスのふるいは、素数を決定するためのより最適化された方法であり、古くから知られています。また、数値が素数であるかどうかを判断するためのより効率的な方法があります。それでも、これらの方法はコストがかかります。場合によっては、代わりに擬素数を使用できます。

このチュートリアルでは、フェルマーの小定理とフェルマーの素数判定について学びます。このテストを使用して、いくつかの非素数をすばやく特定できます。

2. フェルマーの小定理

Fermatは、数値 が素数である場合、範囲内の任意の数値に対して次の等式が成り立つことを示唆しました。

上記の式で、mod演算子はモジュロ演算を表します。モジュロで1に共役であると読みます。したがって、で割ると余りは1になります。

この等式がどの値にも当てはまらない場合は、合成数です。たとえば、23が素数であるかどうかをテストするには、次のように計算する必要があります。

の値が異なる場合。初心者には=2を選択しましょう：

別の番号を試してみましょう。今回は=9を選択します。

に対して異なる値を試しても、この場合の結果は変わりません。の22乗は、モジュラス23の1に相当します。

ただし、すべての可能な値に対して等式が成り立つが、素数ではない例はたくさんあります。たとえば、数値561はフェルマーの素数テストに合格します。つまり、次のような値は見つかりません。

しかし、561はのように合成数です。複合的であるにもかかわらずフェルマー検定に合格するそのような数は、カーマイケル数と呼ばれます。

カーマイケル数が存在するにもかかわらず、フェルマーの数は、数が素数である可能性があるかどうかを判断するために引き続き使用されます。多数の場合、いくつかのランダムな値を試し、テストに合格した場合は擬素数であると結論付けます。

3. フェルマーの素数性テスト

フェルマーの小定理を使用して素数性テストを実装するのは簡単です。

それでも、上記の等式が。の値に当てはまるかどうかを確認することはできません。これは非常に非効率的なアルゴリズムにつながります。代わりに、いくつかのランダムな値を試し、それらの中に反例が見つからない場合は結論を出します。

さまざまなランダムな整数を繰り返し処理します。明らかに、の選択はアルゴリズムの全体的な実行時間に影響します。べき乗演算の残差を計算する方法によって、全体的な実行時間の複雑さが決まります。

計算の簡単な方法には、指数を計算するための乗算演算と、余りを見つけるための除算演算が含まれます。代わりに、2乗べき乗によって結果をより効率的に計算できます。

コンピューティングの複雑さは。冪剰余による計算には、冪剰余演算を約2回適用します。この方法では、2乗モジュロを計算した後、各反復の残差を計算します。

したがって、残差を計算するための複雑さはです。

その結果、フェルマーアルゴリズムの実行時間はです。

4. 実装

フェルマーの素数性テストは、Javaなどのプログラミング言語で簡単にコーディングできます。

パフォーマンスを向上させるには、いくつかのエッジケースをカバーし、組み込みのべき関数の代わりにべき乗剰余を使用する必要があります。

public class FPT {

    static int mPower(int x, int e, int m) {
        int res = 1;

        while (e > 0) {
            if ((e % 2) == 1) {
                res = (res * x) % m;
                e--;
            } else {
                x = (x * x) % m;
                e = e / 2;
            }
        }
        return res;
    }

    static boolean isPrime(int n, int k) {
        if (n % 2 == 0 && n != 2)  {
            return false;
        }

        if (n <= 3)  {
            return true;
        }

        while (k > 0) {
            int a = (int) Math.random() * (n - 3) + 2;
            if (mPower(a, n - 1, n) != 1) {
                return false;
            }

            k--;
        }

        return true;
    }
}