情報セキュリティにおけるオイラーの定理とは？RSA暗号を支える数論の基礎を解説

オイラーの定理とは

オイラーの定理は、フェルマーの小定理を一般化した定理であり、正の整数を法（mod）とする整数の冪乗を扱います。初等整数論の分野で幅広く応用されており、特に現代の情報セキュリティの中核を担うRSA暗号方式の理論的基盤として極めて重要な役割を果たしています。

この定理は、互いに素（最大公約数が1）である任意の a と n に対して、次の式が常に成り立つことを主張しています。

a^φ(n) ≡ 1 （mod n）

ここで φ(n) はオイラーのトーシェント関数（オイラー関数）と呼ばれるもので、n より小さい正の整数のうち、n と互いに素なものの個数を数える関数です。

オイラーの定理の証明の流れ

まず、n より小さく n と互いに素な正の整数の集合を次のように定義します。

R = {x₁, x₂, …, x_φ(n)}

集合 R の各要素 x_i は、n 未満の一意な正の整数であり、gcd(x_i, n) = 1 を満たします。この各要素に a を掛け、n で剰余を取った集合を S とします。

S = {a·x₁ mod n, a·x₂ mod n, …, a·x_φ(n) mod n}

集合 S の性質

a が n と互いに素であり、x_i も n と互いに素であるため、その積 a·x_i も必ず n と互いに素になります。したがって、集合 S のすべての要素は「n より小さく、かつ n と互いに素な整数」であることが分かります。

さらに、集合 S には重複がありません。もし a·x_i mod n = a·x_j mod n が成り立てば、x_i = x_j となることが示せるからです。

以上の性質から、両集合の全要素の積は法 n の下で一致します。

Π_i=1^φ(n) (a·x_i mod n) = Π_i=1^φ(n) x_i （mod n）

左辺を変形すると、a^φ(n) と全要素の積 Π x_i の積の形になり、次のように整理できます。

a^φ(n) · Π_i=1^φ(n) x_i ≡ Π_i=1^φ(n) x_i （mod n）

Π x_i は n と互いに素であるため両辺から消去でき、最終的に次の結論が得られます。

a^φ(n) ≡ 1 （mod n）

オイラーのトーシェント関数とは

オイラーのトーシェント関数は、与えられた整数 n 以下の正の整数のうち、n と互いに素なものの個数を数える乗法的関数です。「オイラーのファイ関数」とも呼ばれ、記号 ϕ（ファイ）で表されます。

この関数は暗号技術において本質的な役割を担っています。n より小さく、かつ n と互いに素な整数の集合は Z_n* として定義され、トーシェント関数はその要素数を求める手段となります。

トーシェント関数の活用場面

• RSA暗号方式：鍵生成の過程で φ(n) の計算が不可欠であり、セキュリティの根幹を支えています。
• 素数理論：素数に関する諸性質の解析に役立ちます。
• 大規模計算：巨大な数を扱う計算の効率化に貢献します。
• 代数的計算：整数論や代数学における各種計算に応用できます。

なお、トーシェント関数は理論的な用途が中心であり、実務での直接的な適用範囲は限られています。また、その挙動は抽象的な説明よりも、具体的な数値例を通じて理解する方が効果的です。

オイラーのトーシェント関数の計算ルール

φ(n) は、以下の4つの基本ルールを用いて Z_n* の要素数を計算できます。

• φ(1) = 0
• φ(P) = P − 1　（P が素数の場合）
• φ(m × n) = φ(m) × φ(n)　（m と n が互いに素の場合）
• φ(P^e) = P^e − P^e−1　（P が素数の場合）

これらのルールを組み合わせることで、任意の n について φ(n) の値を求められます。まず n を素因数分解します。

n = P₁^e1 × P₂^e2 × … × P_k^ek

すると、φ(n) は次の一般式で表されます。

φ(n) = (P₁^e1 − P₁^e1−1) × (P₂^e2 − P₂^e2−1) × … × (P_k^ek − P_k^ek−1)

まとめ：素因数分解の困難さがセキュリティを支える

φ(n) を求める計算量は、n の素因数分解の困難さに直接依存します。大きな合成数を素因数分解することは計算機でも非常に難しく、この計算上の困難さこそが、RSA暗号などの公開鍵暗号方式の安全性を支える基盤となっているのです。オイラーの定理とトーシェント関数は、単なる数学的美しさにとどまらず、現代のデジタル社会の情報セキュリティを陰で支える重要な概念だといえます。