フェルマーの小定理とは？

背景

[大まかな流れ]
東大入試数学問題→素数の計算→エニグマ暗号→RSA暗号
→フェルマーの小定理。
[文章版]
ずーとエニグマ暗号の理論やスクリプトモデルを読んでた。そういえばRSA暗号って？使うのは2組の素数ですよね。現代なら大きな桁の素数だって簡単に求められてしまいそうだが、安全性はどうなのだろう。
まずフェルマーの小定理から素数を「早く」見つけてみる。
では計算してみよう。

フェルマーの小定理

フェルマーの小定理 - Wikipedia

pを素数、aを整数とすると、

$$
a^{p}\equiv a\pmod p
$$

が成り立つという定理です。
また、 aとpが互いに素の時に、

$$
a^{p-1}\equiv 1 \pmod p
$$

が成立する。

証明

wikipediaに書いてあるとおり。

フェルマーテスト

$$
a^{n-1}\neq 1 \pmod n
$$

適当な（乱数のa）とnでこの計算を行い、=1にならなければ、素数ではないという事です。試行する回数が多い程、素数以外を弾けます。下のコードでは5回。

コード

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <sys/time.h>
#include <stdbool.h>
#include <math.h>
#include <time.h>

#define MAX_THREADS 1 // 使用するスレッド数
#define MAX_NUMBER 100000000 // 素数を調べる範囲
#define FERMI_TRIALS 5 // フェルマーテストの試行回数

bool is_prime_fermat(int n, int trials) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0) return false;

    for (int i = 0; i < trials; i++) {
        int a = rand() % (n - 3) + 2; // 2 <= a <= n-2
        if ((int)pow(a, n - 1) % n != 1) {
            return false;
        }
    }
    return true;
}

int is_prime(int n) {
    if (n <= 1) return 0; // 1以下の数は素数ではない
    if (n <= 3) return 1; // 2と3は素数
    if (n % 2 == 0 || n % 3 == 0) return 0; // 2または3で割り切れる数は素数ではない

    // 6k ± 1の形の数をチェックする
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return 0;
        }
    }

    return 1;
}

struct timeval start_time, end_time;

void *find_primes(void *arg) {
    int thread_id = *(int *)arg;
    printf("Thread %d started\n", thread_id);

    for (int i = thread_id + 1; i <= MAX_NUMBER; i += MAX_THREADS) {
        if (is_prime_fermat(i, FERMI_TRIALS) && is_prime(i)) {
        //if (is_prime(i)) {
            // printf("%d is prime\n", i);
        }
    }

    pthread_exit(NULL);
}

int main() {
    pthread_t threads[MAX_THREADS];
    int thread_ids[MAX_THREADS];

    srand(time(NULL)); // ランダムシードの初期化

    gettimeofday(&start_time, NULL);

    // スレッドの作成と実行
    for (int i = 0; i < MAX_THREADS; ++i) {
        thread_ids[i] = i;
        pthread_create(&threads[i], NULL, find_primes, &thread_ids[i]);
    }

    // スレッドの終了を待つ
    for (int i = 0; i < MAX_THREADS; ++i) {
        pthread_join(threads[i], NULL);
    }

    gettimeofday(&end_time, NULL);

    long seconds = end_time.tv_sec - start_time.tv_sec;
    long microseconds = end_time.tv_usec - start_time.tv_usec;
    double elapsed = seconds + microseconds * 1e-6;
    
    printf("Total execution time: %.6f seconds\n", elapsed);

    return 0;
}

コンパイル

%gcc -o fermar_prime fermar_prime.c -pthread -lm
%./fermar_prime

コマンド

実行結果（1スレッドです）

Thread 0 started
Total execution time: 0.743117 seconds

出力

参考：フェルマーテストを使用しない場合

Thread 0 started
Total execution time: 11.772389 seconds

出力

11.77/0.743 = 15.8

15倍程度、高速化されるようです！

所感

アルゴリズムは重要

エニグマ暗号の解読・・・
やるか・・・