素数判定：試し割りからミラーラビン法まで

約5分
数学アルゴリズム

素数（prime number）は「1 と自分自身でしか割り切れない自然数」です。一見単純ですが、効率的な判定や巨大な素数の扱いは現代暗号の基盤になっています。本記事では素数判定の方法を整理します。

素数の定義

p > 1 で、約数が 1 と p のみの自然数：

  • 素数：2, 3, 5, 7, 11, 13, 17, 19, 23, …
  • 合成数：4 (2×2), 6 (2×3), 8 (2×4), 9 (3×3), …
  • 1 は素数ではない（定義上の例外）
  • 2 は唯一の偶数の素数

単純な試し割り

「2 から n-1 まで割れるか試す」：

function isPrime(n) {
	if (n < 2) return false;
	for (let i = 2; i < n; i++) {
		if (n % i === 0) return false;
	}
	return true;
}

時間計算量 O(n)。n が大きいと遅い。

平方根までで十分

n = a × b で a ≤ b なら a ≤ √n：

function isPrime(n) {
	if (n < 2) return false;
	for (let i = 2; i * i <= n; i++) {
		if (n % i === 0) return false;
	}
	return true;
}

時間計算量 O(√n)。100 万以下なら一瞬。

さらなる高速化：6k ± 1

2 と 3 を除けば、すべての素数は 6k ± 1 の形：

function isPrime(n) {
	if (n < 2) return false;
	if (n < 4) return true; // 2, 3
	if (n % 2 === 0 || n % 3 === 0) return false;
	for (let i = 5; i * i <= n; i += 6) {
		if (n % i === 0 || n % (i + 2) === 0) return false;
	}
	return true;
}

i = 5, 7, 11, 13, 17, 19, ... を試す（6 ずつ増やして 2 つチェック）。試し割りより約 3 倍速い。

エラトステネスのふるい

「N 以下の全素数」を求めるなら：

function sieve(n) {
	const isPrime = new Array(n + 1).fill(true);
	isPrime[0] = isPrime[1] = false;
	for (let i = 2; i * i <= n; i++) {
		if (isPrime[i]) {
			for (let j = i * i; j <= n; j += i) {
				isPrime[j] = false;
			}
		}
	}
	return isPrime.map((p, i) => (p ? i : null)).filter((x) => x);
}

時間計算量 O(N log log N)、空間 O(N)。100 万以下の素数を瞬時に列挙。

ミラーラビン法（確率的）

巨大な数（例：10^200）の判定には、確率的アルゴリズムを使う：

n - 1 = 2^r × d  （d は奇数）

a を選ぶ
x = a^d mod n を計算
x が 1 または n-1 なら「素数の可能性」
そうでなければ x = x^2 mod n を r-1 回繰り返す
途中で n-1 になれば「素数の可能性」
最後まで n-1 にならなければ「合成数」

複数の a で試して全部「素数の可能性」ならほぼ確実に素数。

時間計算量 O(k log³ n)（k はテスト回数）。1000 桁の数も 1 秒未満で判定可能。

AKS 素数判定法（決定的・多項式時間）

2002 年に発表された画期的なアルゴリズム：

  • 決定的：間違えない
  • 多項式時間：大きな数でも実用範囲

ただし定数倍が大きく、実務ではミラーラビン法を使うことが多い。「P 問題と判明した」という理論的成果。

メルセンヌ素数

2^p - 1 の形の素数（p は素数）。例：

  • p=2: 2² - 1 = 3
  • p=3: 2³ - 1 = 7
  • p=5: 2⁵ - 1 = 31
  • p=7: 2⁷ - 1 = 127

特殊なテスト（リュカ・レーマー法）で高速に判定可能。現在見つかっている最大の素数はメルセンヌ素数：

  • M82589933 = 2^82589933 - 1（2486 万 2048 桁、2018 年発見）

GIMPS（Great Internet Mersenne Prime Search）プロジェクトが分散コンピューティングで探索中。

双子素数

差が 2 の素数のペア：(3, 5), (5, 7), (11, 13), (17, 19), …

「双子素数は無限にある」という双子素数予想は未解決。

「6k ± 1」のペアであることが多いが、必ずしもすべてが双子素数ではない。

素数定理

x 以下の素数の個数 π(x) の近似：

π(x) ≒ x / ln(x)

例：

  • 100 以下：π(100) = 25（実際）vs 100/ln(100) ≒ 21.7
  • 1000 以下：π(1000) = 168 vs 1000/ln(1000) ≒ 144.8

x が大きくなるほど精度が上がる。

暗号での応用

RSA 暗号の鍵生成：

  1. 巨大な素数 p, q を 2 つ生成（512〜2048 ビット）
  2. n = p × q を計算（公開）
  3. n から p, q を求めるのが難しいことを利用

「2048 ビットの素数を生成」するためミラーラビン法が標準。

楕円曲線暗号（ECC）も素数体上で動作。

素数の分布

素数は不規則に分布するが、巨視的にはパターンがある：

  • ベルトランの仮説：n と 2n の間に必ず素数がある
  • ディリクレの算術級数定理：等差数列に無限に素数がある
  • リーマン予想（未解決）：素数の分布の精密な記述

実装上の注意

  • 整数オーバーフロー：i * i が大きくなると桁あふれ。BigInt を使うか、上限をチェック
  • 負の数：素数は正の整数のみ
  • キャッシュ：複数回判定するなら結果をメモ化
  • 乱数の質：暗号用の素数生成では暗号学的に安全な乱数（CSPRNG）を使う

まとめ

  • 単純な試し割りは O(n)、平方根までで O(√n)
  • 6k ± 1 の最適化で約 3 倍速い
  • 全素数列挙はエラトステネスのふるい
  • 巨大な数はミラーラビン法（確率的）
  • 暗号で 2048 ビット素数を生成

特定の数が素数かどうかの判定には、本サイトの素数判定ツールが使えます。