最小原始根の計算 - ト部蛸焼のブログ

今回は，整数に関する話です。最小原始根と呼ばれるものを考えます。

最小原始根
参考文献

最小原始根

定義

説明の都合上，群論の基本的な用語である「位数」を定義します。

定義群 $G$ の元 $g$ について，ある正整数 $n$ が存在して $g^{n} = e$ となるとき*1， $g$ の位数 (order) $\operatorname{ord}(g)$ をそのような $n$ の最小値とする。一方で，どんな正整数 $n$ に対しても $g^{n} = e$ とならないとき， $g$ の位数 $\operatorname{ord}(g)$ は $\infty$ であるとする。

すなわち，元 $g \in G$ の位数とは「その回数だけ累乗して初めて1になるもの」と考えることができます。ここでは証明しませんが，有限群の元の位数はその群 $G$ の要素の数 $\left| G \right|$ の約数になります*2。また，これもここでは証明はしませんが，次の命題も成立します。

命題素数 $p$ に対して $(\mathbb{Z}/p\mathbb{Z})^{\times} = (\mathbb{Z}/p\mathbb{Z}) \setminus \{0\}$ はある元 $a \in (\mathbb{Z}/p\mathbb{Z})^{\times}$ を用いて $(\mathbb{Z}/p\mathbb{Z})^{\times} = \{ a^{n} \,|\,n=1,\dots,p-1\}$ と表される*3。

例: $(\mathbb{Z}/5 \mathbb{Z})^{\times}$ について， $a^{n}$ の値を表にまとめると下の表のようになる。したがって，この表から
\begin{align}
(\mathbb{Z}/5 \mathbb{Z})^{\times} = \{ 2^{n} \,|\,n=1,\dots,4\} = \{ 3^{n} \,|\,n=1,\dots,4\}
\end{align}であることが分かる。

$a$ \ $n$	1	2	3	4
1	1	1	1	1
2	2	4	3	1
3	3	4	2	1
4	4	1	4	1

定義素数 $p$ に対して $(\mathbb{Z}/p\mathbb{Z})^{\times}$ を考える。上の命題を満たす $a$ のことを， $p$ を法とする原始根 (primitive root) という。

$\mathbb{Z}/p\mathbb{Z}$ と書きましたが，難しければ単に $p$ で割ったときの余りの話をしていると思えばよいでしょう。今回はややふんわりした言葉で定義しましたが，群論の言葉を使ってしっかりと述べれば，原始根とは「乗法群 $(\mathbb{Z}/p\mathbb{Z})^{\times}$ の生成元」ということです。言い換えればこれは， $p-1$ 乗しないと1にならない数であるということです*4。以下では $\mathbb{Z}/p\mathbb{Z}$ を $\mathbb{Z}_{p}$ と書いてしまい，その元も整数と同じ記号で書いてしまうことにします*5。

原始根の求め方

上の例で述べたように乗法表を全て埋めなければ原始根は求まらないのでしょうか。答えはNoです。例えば， $a$ が $p-1$ より小さい数 $k$ で $a^{k} \equiv 1 \pmod p$ であるとき， $a^{\ell}$ と表される数はみな $(a^{\ell})^{k} \equiv (a^{k})^{\ell} \equiv 1 \pmod p$ を満たします。このことから， $a$ が原始根でなければ， $a$ の累乗の形の元も原始根ではありません。

実は次の命題が成り立ちます。

命題 $p$ を素数とし， $p-1$ の素因数分解を $p-1 = \prod_{i=1}^{k} p_{i}^{e_{i}}$ とする。このとき， $a \in \mathbb{Z}_{p}^{\times}$ について，次が成り立つ。

$a:$ 原始根 $\iff$ $\forall i \in \{1,\dots,k\}, \quad a^{\frac{p-1}{p_{i}}} \not\equiv 1 \pmod p$

証明

$\Longrightarrow$ : $\dfrac{p-1}{p_{i}}$ は $1 \le \dfrac{p-1}{p_{i}} < p-1$ を満たす整数である。 $a$ が $p$ を法とする原始根である，つまり， $p-1$ 乗しないと1にならないことから， $a^{\frac{p-1}{p_{i}}} \not\equiv 1 \pmod p$ である。

$\Longleftarrow$ : 対偶を示すことにする。 $a$ が原始根でないとする。 $a$ の位数 $\operatorname{ord}(a)$ は $\left| \mathbb{Z}_{p}^{\times} \right| = p-1$ の約数なので，素因数分解すると， $\operatorname{ord}(a) = \prod_{j=1}^{k} p_{j}^{e_{j}^{\prime}}$ （ $e_{j}^{\prime} \le e_{j}$ ）と書くことができる。 $N = \{ 1,\dots,k \}$ とし， $A = \{ j \in N \,|\, e_{j}^{\prime} < e_{j} \}$ ， $B = \{ j \in N \,|\, e_{j}^{\prime} = e_{j} \}$ とおく。 $A = \emptyset$ ならば $\operatorname{ord}(a) = p-1$ であり $a$ は原始根となるので矛盾。よって，ある $i \in N$ が存在して， $i \in A$ である。いま， $e_{i}^{\prime} < e_{i}$ より， $e_{i} - e_{i}^{\prime} - 1 \ge 0$ であることなどに気をつけると， $\ell := p_{i}^{e_{i} - e_{i}^{\prime} - 1} \prod_{j \in A \setminus \{i\}} p_{j}^{e_{j} - e_{j}^{\prime}}$ は整数である。また，
\begin{align}
\operatorname{ord}(a) \cdot \ell = \left( \prod_{j \in A} p_{j}^{e_{j}^{\prime}} \right) \left( \prod_{j \in B} p_{j}^{e_{j}^{\prime}} \right) p_{i}^{e_{i} - e_{i}^{\prime} - 1} \left( \prod_{j \in A \setminus \{i\}} p_{j}^{e_{j} - e_{j}^{\prime}} \right) = \frac{p-1}{p_{i}}.
\end{align}これより，
\begin{align}
1 \equiv (a^{\operatorname{ord}(a)})^{\ell} \equiv a^{\frac{p-1}{p_{i}}} \pmod p.
\end{align}証明終

この命題を用いると，最小原始根を計算するアルゴリズムが導かれます。

最小原始根を計算するアルゴリズム

最小原始根を計算するアルゴリズム入力: 素数 $p$
出力: $\mathbb{Z}_{p}^{\times}$ の最小原始根
Step 1: $p-1$ の素因数 $p_{1}, \dots, p_{k}$ を求める。
Step 2: $a = 2$ とする。
Step 3: $i = 1, \dots, k$ に対して $a^{\frac{p-1}{p_{i}}} \equiv 1 \pmod p$ かどうかを調べる。もしそのような $i$ があれば $a \leftarrow a+1$ としてStep 3をもう一度行う。
Step 4: $a$ を最小原始根とする。

これを実際にPythonのコードで書いてみたものが下のコードです。今回は素因数分解をするためにSympyを使っています。試し割りをすれば手製のものも作れるのでしょうが，手間を省きました*6。

import numpy as np
import sympy as sp

def mod_pow(a,b,mod): # a^{b}
  b = int(b)
  x = 1
  for times in range(0,b):
    x = x * a % mod
  return x

# 計算のために，乱数を使って適当な素数pを選ぶ
p = sp.prime(int(np.random.rand()*100+1))

# p-1 の素因数を求める
prime_factor_list = sp.primefactors(p-1) # ありがとうSympy
k = len(prime_factor_list)

# ここからが上のアルゴリズムのStep 3にあたる
a = 2
i = 0
while (i!=k):
  if (mod_pow(a, (p-1)//prime_factor_list[i], p) == 1):
    a += 1
    i = 0
  else:
    i += 1
print(a) # a がZ/pZの最小原始根

このコードを用いて実際に最小原始根を計算すると，次の表のようになりました。この表では， $\mathbb{Z}_{p}^{\times}$ の $p$ の値と対応する最小原始根 $a$ の値を並べました。 $p$ は2から15番目の素数までについて計算しています*7。

$p$	3	5	7	11	13	17	19	23	29	31	37	41	43	47
$a$	2	2	3	2	2	3	2	5	2	3	2	6	3	5

参考文献

『工学基礎代数系とその応用』（著平林隆一，数理工学社）p.96

*1: $e$ は群 $G$ の単位元を指す。

*2:この $\left| G \right|$ のことを群の位数と呼びます。ややこしい……。

*3:このようにある群が一つの元の累乗という形で尽くされるとき，その群は巡回群 (cyclic group) であるといいます。

*4:群 $G$ の元 $a$ によって生成される $G$ の部分群を $\langle a \rangle$ と書くと，この $\langle a \rangle$ の位数は元 $a$ の位数 $\operatorname{ord}(a)$ と等しくなります。ただし，共に有限でない場合は濃度の違いを無視して単に無限だから等しいということにします。