情報セキュリティにおけるフェルマーの小定理とは？定義・証明・計算例を徹底解説

フェルマーの小定理（Fermat's little theorem）は、初等整数論における最も基本的な定理の一つで、素数を法とする整数のべき乗計算を可能にする強力な道具です。この定理はオイラーの定理の特殊なケースにあたり、素数判定や公開鍵暗号方式など、情報セキュリティ分野の応用において不可欠な役割を果たしています。

フェルマーの小定理の定義

フェルマーの小定理は、次のように定義されます。p が素数であり、a が p で割り切れない正の整数であるとき、以下の関係式が成り立ちます。

a^p−1 ≡ 1 (mod p)

また、第2の形式として、p が素数で a が任意の整数である場合には、次の式が成立します。

a^p ≡ a (mod p)

フェルマーの小定理の証明

Z_p を整数の集合 {0, 1, …, p−1} とします。この各要素に a を掛けて p で割った余りを考えると、その結果には Z_p のすべての要素が何らかの順序で含まれます。さらに a × 0 ≡ 0 (mod p) であるため、(p−1) 個の数 {a mod p, 2a mod p, …, (p−1)a mod p} は、{1, 2, …, (p−1)} の並べ替えと一致します。

両辺の数を掛け合わせて p を法として整理すると、次のようになります。

a × 2a × … × (p−1)a = [(a mod p) × (2a mod p) × … × ((p−1)a mod p)] mod p
= [1 × 2 × … × (p−1)] mod p
= (p−1)! mod p

一方、左辺は次のように変形できます。

a × 2a × … × (p−1)a = (p−1)! ・ a^p−1

したがって、

(p−1)! ・ a^p−1 ≡ (p−1)! (mod p)

(p−1)! と p は互いに素であるため、両辺から (p−1)! を約分でき、目的の結論が得られます。

a^p−1 ≡ 1 (mod p)

集合の観点からの補足

p 未満の正の整数の集合 {1, 2, …, p−1} の各要素に a を掛けて p で割った余りを求めると、集合 X = {a mod p, 2a mod p, …, (p−1)a mod p} が得られます。p が a を割り切らないため、X の要素がゼロになることはありません。

また、X 内のどの2つの整数も重複しません。仮に ja ≡ ka (mod p)（1 ≤ j < k ≤ p−1）が成り立つと仮定すると、p と a が互いに素であることから、両辺から a を消去して j ≡ k (mod p) が導かれます。しかし j と k はどちらも p 未満の異なる正の整数であるため、これは矛盾です。

以上より、X の (p−1) 個の要素はすべて正の整数であり、互いに異なることが証明されました。

数値による確認

フェルマーの小定理によれば、p が素数で a が p で割り切れない正の整数のとき、a^p−1 ≡ 1 (mod p) が成り立ちます。

例えば p = 11、a = 3 の場合、次の関係が成り立ちます。

3¹⁰ ≡ 1 (mod 11)

この性質を利用すると、大きな指数のべき乗計算も簡単に処理できます。

3²⁰¹ = (3¹⁰)²⁰ × 3 ≡ 1²⁰ × 3 ≡ 3 (mod 11)

具体的な計算例

フェルマーの小定理は、一部の冪乗計算について答えを素早く導き出すのに役立ちます。以下の例でその活用方法を見ていきましょう。

例1：6¹⁰ mod 11 を求める

解答：
ここでは、6¹⁰ mod 11 = 1 となります。これは p = 11 の場合のフェルマーの小定理の第1形式をそのまま適用できる典型例です。

例2：3¹² mod 11 を求める

解答：
指数（12）と法（11）が一致しないため、式を変形してからフェルマーの小定理を適用します。

3¹² mod 11 = (3¹¹ × 3) mod 11 = (3¹¹ mod 11) × (3 mod 11) = (3 × 3) mod 11 = 9

このように、フェルマーの小定理を使うことで、巨大な指数を持つ冪乗の剰余計算を効率的に行えます。RSA暗号などの公開鍵暗号システムの安全性と実装は、まさにこのような数論的性質の上に成り立っているのです。