素数判定法5 フェルマーテストの続きです。

n が素数であるかを調べるために2 ^ nを計算しなければならない、ということでした。

n = 13のとき本来であれば

2 ^ 13 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2

2を12回掛けなければいけません。

これを簡単にするのが繰り返し二乗法です。

乗数を分解して、

2 ^ 13 = (2 ^ 1) * (2 ^ 4) * (2 ^ 8)  = 2 * 16 * 256 に分解するのが繰り返し二乗法です。

繰り返し二乗法を使えば計算回数を減らすことができます。

フェルマーの小定理を貼り付けておきます。

2 ^ (n - 1) mod n = 1 

c言語プログラム 
#include<stdio.h>

int main()
{
long long m, n;
long long s = 1;
long long a = 2;
printf("数字を入力してください\n");
scanf("%lld", &n);
m = n -1;
while(m != 0) {
if (m & 1) {
s = (s * a) %n;
}
printf("m = %lld s = %lld a = %lld\n", m, s, a);
a = (a * a) % n;
m = m>>1;
}
if (s == 1) {
printf("%lldは素数です\n", n);
} else {
printf("%lldは素数ではありません\n", n);
}
}

$ gcc fermat.c -o fermat

$ ./fermat

数字を入力してください

9999637

9999637は素数です 

素数判定法6 フェルマーテスト GMPライブラリ に続きます。

参考サイト
繰り返し二乗法