Int 素数判定

概要

多倍長整数の素数判定は暗号・数論計算の基盤である。 しかし、多倍長整数に対する決定的な素数判定は計算コストが極めて重く、 実用的な時間内に完了しない場合が多い。

calx では 2 つのアプローチを提供する:

  • isProbablePrime() — Miller-Rabin 確率的素数判定。 デフォルト 25 ラウンドで誤判定確率 $4^{-25} \leq 2^{-50} \approx 10^{-15}$。高速。
  • isProvablePrime() — APRCL 決定的素数証明。 数学的に厳密な証明を返す。計算コストは高いが数百桁でも現実的。

判定の前段階として、小素数テーブルによる試し割りを行い、 大半の合成数を低コストで除外する。

API の使い方については Int API リファレンス — 素数判定 を参照。

小素数による前処理

Miller-Rabin は 1 ラウンドあたりモジュラ冪乗を要するため、 すべての入力に対して直ちに実行するのは非効率である。 そこで、事前に計算された小素数テーブルを用いた試し割りを前処理として行う。

具体的には、$n$ を小素数 $p_1, p_2, \ldots, p_k$ で割り、 $n \bmod p_i = 0$ かつ $n \neq p_i$ であれば直ちに合成数と判定する。 この剰余演算は 1 ワードの除算で済むため極めて軽い。

小素数による前処理の効果は大きい。 たとえば、2, 3, 5 による試し割りだけで奇数の約 77% の合成数が除外される。 テーブルを数百個の素数に拡張すると、大半の合成数がこの段階で排除される。

入力が十分に小さい場合 (テーブルの最大素数の二乗以下)、 試し割りだけで素数判定が完結するため、Miller-Rabin を呼び出す必要がない。

Miller-Rabin 素数判定法

Miller-Rabin はフェルマーの小定理を強化した確率的素数判定法である。

フェルマーの小定理

$p$ が素数ならば、$\gcd(a, p) = 1$ であるすべての $a$ に対して:

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

対偶を取ると、$a^{n-1} \not\equiv 1 \pmod{n}$ ならば $n$ は合成数である。 しかし、逆は成り立たない。$a^{n-1} \equiv 1 \pmod{n}$ を満たす合成数 $n$ が存在する (擬素数)。

Miller-Rabin の強化

Miller-Rabin は次の観察に基づいて判定を強化する。 $n - 1$ を $n - 1 = 2^s \cdot d$ ($d$ は奇数) と分解する。 $n$ が素数ならば、任意の底 $a$ ($1 < a < n$) に対して次のいずれかが成立する:

$$a^d \equiv 1 \pmod{n}$$

または、ある $r$ ($0 \leq r < s$) が存在して:

$$a^{2^r \cdot d} \equiv -1 \pmod{n}$$

この条件は「$1$ の平方根は $\pm 1$ のみ」という性質から導かれる。 素数 $n$ において $x^2 \equiv 1 \pmod{n}$ ならば $x \equiv \pm 1 \pmod{n}$ であるため、 $a^d$ から繰り返し二乗していく過程で $1$ に到達する直前の値は必ず $-1$ でなければならない。

アルゴリズム

入力: 奇数 $n \geq 3$、ラウンド数 $k$

  1. $n - 1 = 2^s \cdot d$ と分解する ($d$ は奇数)。
  2. $k$ 回繰り返す:
    1. 底 $a$ をランダムに選ぶ ($2 \leq a \leq n - 2$)。
    2. $x \leftarrow a^d \bmod n$ を計算する (モジュラ冪乗)。
    3. $x = 1$ または $x = n - 1$ ならば、このラウンドは通過。次のラウンドへ。
    4. $s - 1$ 回繰り返す:
      1. $x \leftarrow x^2 \bmod n$
      2. $x = n - 1$ ならば、このラウンドは通過。次のラウンドへ。
    5. ここに到達したら $n$ は合成数 ($a$ は witness)。
  3. $k$ ラウンドすべて通過したら「おそらく素数」と判定する。

誤判定確率

Rabin (1980) は、合成数 $n$ に対して witness とならない底 $a$ の割合が高々 $1/4$ であることを証明した。 したがって:

  • 1 ラウンドの誤判定確率: $\leq 1/4$
  • $k$ ラウンドの誤判定確率: $\leq 4^{-k}$

calx のデフォルト $k = 25$ では:

$$4^{-25} = 2^{-50} \approx 8.9 \times 10^{-16}$$

これは 1,000 兆回に 1 回未満の誤判定確率であり、 実用上「確実」とみなせる水準である。

計算量

各ラウンドの主要コストはモジュラ冪乗 $a^d \bmod n$ の計算である。 二分法 (binary method) による冪乗は $O(\log n)$ 回のモジュラ乗算を要し、 各モジュラ乗算のコストを $M(n)$ とすると:

$$\text{1 ラウンドのコスト} = O(\log n \cdot M(n))$$

$k$ ラウンド全体では $O(k \cdot \log n \cdot M(n))$ である。

関連記事: Miller-Rabin 素数判定法 | 多倍長整数の高度なアルゴリズム

Fermat 素数判定

Fermat 素数判定はフェルマーの小定理を直接利用する、 Miller-Rabin より単純だが弱い判定法である。

底 $a$ に対して $a^{n-1} \bmod n$ を計算し、 結果が $1$ でなければ $n$ は合成数、$1$ ならば「おそらく素数」と判定する。

$$a^{n-1} \equiv 1 \pmod{n} \quad \Rightarrow \quad n \text{ はおそらく素数}$$

Fermat 判定の致命的な弱点は Carmichael 数 (カーマイケル数) の存在である。 Carmichael 数とは、すべての底 $a$ ($\gcd(a, n) = 1$) に対して $a^{n-1} \equiv 1 \pmod{n}$ を満たす合成数である。 最小の Carmichael 数は $561 = 3 \times 11 \times 17$ であり、 Carmichael 数は無限に存在することが証明されている (Alford-Granville-Pomerance, 1994)。

Miller-Rabin はフェルマー判定を強化しているため、Carmichael 数に対しても正しく合成数と判定できる。

calx は IntPrime::isFermatPrime() として Fermat 判定を提供している。 デフォルトは $k = 5$ ラウンドである。 Miller-Rabin より 1 ラウンドあたりの計算が若干軽いが (二乗ステップが不要)、 高い信頼性が求められる場面では使用すべきでない。

次の素数・前の素数

IntPrime::nextPrime(n) は $n$ より大きい最小の素数を返す。 IntPrime::prevPrime(n) は $n$ より小さい最大の素数を返す。

アルゴリズム

基本方針は単純である: $n$ から 1 ずつ増加 (または減少) させながら、 各候補に対して素数判定を行い、最初に素数と判定された値を返す。

ただし、偶数は明らかに素数ではないため、 奇数のみを候補として検査する (2 の場合を除く)。

候補数の期待値

素数定理 (Prime Number Theorem) により、$n$ 付近の素数の平均間隔は $\ln n$ である。 したがって、次の素数を見つけるまでに検査する候補数の期待値は $O(\ln n)$ である。

$n$ が $b$ ビットの整数であれば $\ln n \approx b \cdot \ln 2 \approx 0.693 b$ であり、 たとえば 1024 ビットの整数では平均して約 710 個の候補を検査する。 各候補は Miller-Rabin で判定されるが、大半は小素数の試し割りで即座に除外されるため、 実際に Miller-Rabin が実行される回数はごく少ない。

設計判断

Miller-Rabin を選択した理由

素数判定アルゴリズムには複数の選択肢がある。 calx が Miller-Rabin を主要アルゴリズムとして採用した理由を他の候補と比較して説明する。

BPSW (Baillie-PSW) 判定

BPSW は Miller-Rabin (底 $a = 2$) と強 Lucas 判定の組み合わせである。 2026 年現在、BPSW の反例 (BPSW 擬素数) は発見されていない。 しかし:

  • Lucas 判定の実装が追加で必要となり、コードの複雑性が増す
  • 反例が存在しないことは証明されていない (予想にすぎない)
  • Miller-Rabin $k = 25$ の誤判定確率 $2^{-50}$ は実用上十分に小さい

AKS (Agrawal-Kayal-Saxena) 判定

AKS は 2002 年に発表された決定的多項式時間の素数判定アルゴリズムであり、 理論計算機科学における画期的な成果である。 しかし:

  • 計算量は $\tilde{O}(\log^6 n)$ であり、多倍長整数に対しては極めて遅い
  • 実用的な速度で動作するのは小さな数に限られる
  • 確率的手法の誤判定確率が無視できるほど小さいため、決定性の実用的価値は限定的

APRCL 決定的素数証明 (calx で実装済み)

calx は Miller-Rabin に加えて、APRCL (Adleman-Pomerance-Rumely-Cohen-Lenstra) アルゴリズムによる決定的素数証明も isProvablePrime() として提供している。 APRCL は AKS より実用的に高速であり、数百桁の素数に対しても現実的な時間で動作する。

用途に応じた使い分け:

  • isProbablePrime(): 通常の用途。Miller-Rabin $k = 25$ で高速判定
  • isProvablePrime(): 数学的に厳密な証明が必要な場合。計算コストは高い

デフォルト $k = 25$ の根拠

$k = 25$ は誤判定確率 $2^{-50}$ を与える。 この確率は以下と比較して十分に小さい:

  • ハードウェアエラー (メモリビット反転等) による計算誤りの確率のほうがはるかに大きい
  • 暗号応用では通常 $k = 20$–$40$ が推奨される (FIPS 186-4 等)
  • $k$ を増やしてもコストは線形にしか増えないため、余裕を持たせるコストは低い

参考文献

  • Miller, G. L. (1976). “Riemann’s Hypothesis and Tests for Primality”. Journal of Computer and System Sciences, 13 (3), 300–317.
  • Rabin, M. O. (1980). “Probabilistic algorithm for testing primality”. Journal of Number Theory, 12 (1), 128–138.
  • Alford, W. R., Granville, A. and Pomerance, C. (1994). “There are Infinitely Many Carmichael Numbers”. Annals of Mathematics, 139 (3), 703–722.
  • Agrawal, M., Kayal, N. and Saxena, N. (2004). “PRIMES is in P”. Annals of Mathematics, 160 (2), 781–793.