情報セキュリティにおける素数判定テストとは？仕組みと種類をわかりやすく解説

素数判定テスト（primality test）とは

素数判定テストとは、入力された数値が素数であるかどうかを判定するアルゴリズムのことです。中には決定的（deterministic）なテストもあり、この種のテストは、対象の数が素数か合成数かを常に正確に判定できます。

最速の決定的素数判定アルゴリズム「AKS」

現在知られている最速の決定的素数判定テストは、2004年に開発されました。コンピュータ科学者であるAgrawal氏、Kayal氏、Saxena氏の3名によって考案された「AKS素数判定法」は、O˜(log(n)⁶)の時間計算量で動作します。ここでO˜(f(n))とは、ある整数kに対してO(f(n)・log^k(f(n)))として表される記法です。これは大きなブレークスルーとなりましたが、情報セキュリティ分野の要求水準と比較すると、その処理速度は依然として遅いと言わざるを得ません。

なぜ暗号技術には素数が必要なのか

素数が活躍する分野の代表例が暗号技術です。標準的な暗号方式の一つであるRSAアルゴリズムでは、鍵として素数が必要であり、より高いセキュリティを実現するために、一般的に1024ビットを超える大きな素数が使用されます。

しかし、このような巨大な数を扱う場合、単純な手法では対応できません。特に素数判定の過程で行われる除算（/）や剰余演算（%）といった演算において、巨大な数の取り扱いは非常に困難です。

そのため、現時点で実用化されている優れた素数判定アルゴリズムでも、与えられた数が「確率的素数（probable prime）」であるか合成数であるかを判定できるにとどまります。

素数判定テストの主な種類

素数判定テストには、以下のような種類があります。

1. 決定的アルゴリズム（Deterministic Algorithm）

決定的素数判定アルゴリズムは、整数を受け取り、必ず「素数」または「合成数」のいずれかを出力します。このアルゴリズムは、常に正しい答えを返すことが保証されています。

2. 整除性アルゴリズム（Divisibility Algorithm）

最もシンプルな素数判定テストは、以下の手順で行われます。

入力された数nに対し、2からn−1までの整数のうち、nを割り切るものが存在するかどうかを調べます。nがあるmで割り切れるのであればnは合成数であり、割り切れない場合は素数となります。ただし、n−1までのすべてのmを試す必要はなく、√nまでのmを調べれば十分です。なぜなら、nが合成数であれば2つの因数に分解でき、そのうち少なくとも一方は必ず√n以下になると証明されているためです。

3. 確率的アルゴリズム（Probabilistic Algorithm）

確率的アルゴリズムは、ほとんどの場合に正しい答えを返しますが、常に正しいとは限りません。このテストでは、nが「すべての素数が満たすべき条件」の一つ以上を満たしているかどうかを判定します。確率的アルゴリズムは、以下のルールに従って「素数」または「合成数」を返します。

• 判定対象の整数が実際に素数である場合、アルゴリズムは必ず「素数」を返します。
• 判定対象の整数が実際に合成数である場合、確率1−εで「合成数」を返しますが、確率εで「素数」と誤判定する可能性があります。この誤りの確率は、アルゴリズムをm回繰り返し実行することで低減でき、誤り率をΣ^mまで下げることが可能です。

フェルマー素数判定テスト

フェルマー素数判定テストは、「フェルマーの小定理」に基づいた手法です。フェルマーの小定理とは、「nが素数であれば、aⁿ⁻¹ ≡ 1 (mod n) が成り立つ」という定理を指します。入力としてnと a < n を与え、aⁿ⁻¹ ≡ 1 (mod n) が成立するかどうかを検証します。この式が成り立たない場合はnは合成数と断定でき、成り立つ場合はnは「おそらく素数」と判断されます。

残念ながら、フェルマー素数判定テストには誤判定のコストが高いという重大な欠点があり、「おそらく素数」と誤認されてしまう合成数が非常に多く存在します。