ネットワークセキュリティ学習に役立つ原始根とは？定義・求め方・具体例を徹底解説

原始根（げんしこん）とは何か？

原始根とは、ある正の整数 n に対して、n と互いに素なすべての整数が、g のべき乗として法 n で表せるような整数 g のことを指します。言い換えると、整数 g が「法 n における原始根」であるとは、n と互いに素な任意の整数 a に対して、a ≡ g^z (mod n) を満たす整数 z が必ず存在するということです。このとき、g のべき乗は法 n の既約剰余類全体（乗法群）をちょうど一周します。

原始根は素数 p を法とする場合によく扱われ、法 p の原始根の個数は φ(p−1) 個（φ はオイラーのトーシェント関数）であることが知られています。

原始根の求め方：オイラーのトーシェント関数を使う

n が素数のとき、オイラーのトーシェント関数は φ(n) = n − 1 となります。これを利用すると、原始根は次の手順で見つけられます。

1. n − 1 を素因数分解し、その素因数をすべて列挙する。
2. 候補となる整数 g について、各素因数 p ごとに g^((n−1)/p) ≢ 1 (mod n) が成り立つかを計算して確認する。
3. すべての素因数について条件を満たせば、g は法 n の原始根であると判定できる。

これは「g の位数が φ(n) と一致するかどうか」を直接確認する方法であり、位数が n − 1（＝φ(n)）と等しいとき、その元は原始根になります。

具体例で理解する原始根

法 14 の例：位数を調べてみよう

法 14 の既約剰余類は {1, 3, 5, 9, 11, 13} で、φ(14) = 6 です。それぞれの位数を見ると、1 の位数は 1、9 と 11 の位数は 3、13 の位数は 2、そして 3 と 5 の位数は 6 となります。したがって、3 と 5 が法 14 の原始根です。

11 の原始根

φ(11) = 10 なので、各元の 1 乗から 10 乗までを法 11 で計算し、すべての既約剰余類が現れるかを確認します。その結果、2, 6, 7, 8 の 4 つが原始根であることが分かります。

13 の原始根

法 13 の原始根は 2, 6, 7, 11 です。原始根の総数は φ(p−1) = φ(12) = 4 個となり、ここでも理論値と一致します。

17 の原始根

φ(17) = 16 で、3 が原始根であることが分かっています。原始根同士の性質から、「3 の奇数べき（指数が 16 と互いに素なもの）」もすべて原始根になります。具体的には、3¹ = 3、3³ = 10、3⁵ = 5、3⁷ = 11、3⁹ = 14、3¹¹ = 7、3¹³ = 12、3¹⁵ = 6 より、3, 5, 6, 7, 10, 11, 12, 14 の 8 個が法 17 の原始根です。

23 の原始根

φ(23) = 22 なので、a が原始根かどうかを判定するには、a² ≢ 1 (mod 23) かつ a¹¹ ≢ 1 (mod 23) を確認すれば十分です。たとえば 5 について計算すると条件を満たすため、5 は法 23 の原始根です。

29 の原始根

2 が法 29 の原始根であるため、gcd(k, 28) = 1 を満たすすべての k に対して 2^k (mod 29) も原始根になります。つまり原始根は {2^k : k = 1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27} として得られ、具体的には 2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27 の 12 個です。

31 の原始根

法 31 の原始根は 3, 11, 12, 13, 17, 21, 22, 24 の 8 個です。これは φ(p−1) = φ(30) = 8 とも一致しています。

証明例：2 はなぜ 11 の原始根なのか

p = 11 の場合、2 の位数は φ(11) = 10 の約数（1, 2, 5, 10）のいずれかになります。そこで次のように確認します。

• 2² = 4 ≢ 1 (mod 11)
• 2⁵ = 32 ≡ −1 (mod 11)
• 2¹⁰ = (2⁵)² ≡ 1 (mod 11)

2 の位数は 1, 2, 5 のいずれにもなり得ず、10 と確定します。したがって 2 は法 11 の原始根です。

原始根とネットワークセキュリティの関係

原始根は単なる数論の話題にとどまらず、現代の暗号技術の中核を担っています。代表的なのが Diffie–Hellman 鍵交換です。このプロトコルでは、大きな素数 p とその原始根 g が公開パラメータとして用いられ、通信当事者は各自の秘密の指数を掛け合わせた値を交換することで共有鍵を生成します。原始根を使うことで、生成される値の分布が偏らず安全性が高まるのです。この仕組みの安全性は「離散対数問題」を効率的に解くことが困難であるという事実に依存しており、原始根の理解はネットワークセキュリティや暗号理論を学ぶうえで欠かせない基礎知識といえます。