原始根と離散対数 ― 巡回群としての $(\mathbb{Z}/p\mathbb{Z})^*$

$(\mathbb{Z}/p\mathbb{Z})^*$が巡回群であることを証明し，原始根の個数が$\varphi(p-1)$であることを示す．指数（離散対数）の概念を導入し，$(\mathbb{Z}/p^k\mathbb{Z})^*$の構造定理を扱い，離散対数問題（DLP）を解説する．

Folio公式

2026年2月27日

1 原始根の定義

定義 1 (原始根).

正整数

n

に対して

ord_{n} (g) = φ (n)

を満たす整数

g

が存在するとき，

g

を

n

の原始根（primitive root）という．このとき

(Z / n Z)^{*}

は

\overset{g}{ˉ}

で生成される巡回群である．

2 $(ma t hbb Z / p ma t hbb Z)^{*}$ が巡回群であること

補題 2.

体

F

上の

d

次多項式は高々

d

個の根を持つ．

証明.

d

に関する帰納法．

d = 0

は明らか．

d \geq 1

とし，

f (a) = 0

なる根

a

が存在すれば

f (x) = (x - a) g (x)

（

de g g = d - 1

）と因数分解でき，

f

の根は

a

と

g

の根を合わせて高々

1 + (d - 1) = d

個． □

定理 3.

素数

p

に対して

(Z / p Z)^{*}

は位数

p - 1

の巡回群である．

証明.

(Z / p Z)^{*}

は位数

p - 1

の有限アーベル群である．

d ∣ (p - 1)

なる各正整数

d

に対し，

ψ (d) = ∣ {a \in (Z / p Z)^{*} ∣ ord (a) = d} ∣

とおく．位数

d

の元

a

が存在すれば

1, a, a^{2}, \dots, a^{d - 1}

は

x^{d} - 1 = 0

の

d

個の根であり，体上の多項式は

d

次なら高々

d

根なので位数

d

の約数である元はこれらに限る．この中で位数がちょうど

d

である元の個数は

φ (d)

．よって各

d ∣ (p - 1)

に対して

ψ (d) = 0

または

ψ (d) = φ (d)

．

一方

\sum_{d ∣ (p - 1)} ψ (d) = p - 1 = \sum_{d ∣ (p - 1)} φ (d)

（後者はオイラー関数の基本恒等式）なので，すべての

d ∣ (p - 1)

に対して

ψ (d) = φ (d)

．特に

ψ (p - 1) = φ (p - 1) \geq 1

より位数

p - 1

の元が存在する． □

系 4.

(Z / p Z)^{*}

の原始根の個数は

φ (p - 1)

である．

3 指数（離散対数）

定義 5 (指数).

g

を

n

の原始根とし，

g cd (a, n) = 1

とする．

g^{k} \equiv a (mod n)

を満たす最小の非負整数

k

（

0 \leq k < φ (n)

）を

a

の

g

に関する指数（index）または離散対数（discrete logarithm）といい，

ind_{g} (a)

と書く．

定理 6 (指数の性質).

原始根

g

に対して

$ind_{g} (ab) \equiv ind_{g} (a) + ind_{g} (b) (mod φ (n))$ ．
$ind_{g} (a^{k}) \equiv k \cdot ind_{g} (a) (mod φ (n))$ ．
$ord_{n} (a) = φ (n) / g cd (ind_{g} (a), φ (n))$ ．

証明.

(1)

g^{ind_{g} (a)} \equiv a

，

g^{ind_{g} (b)} \equiv b

より

g^{ind_{g} (a) + ind_{g} (b)} \equiv ab \equiv g^{ind_{g} (ab)} (mod n)

．

g

の位数が

φ (n)

なので指数が

mod φ (n)

で一致．(2) は (1) の繰り返し適用．(3)

a^{k} \equiv 1

は

k \cdot ind_{g} (a) \equiv 0 (mod φ (n))

と同値であり，最小の正整数

k

は

φ (n) / g cd (ind_{g} (a), φ (n))

． □

4 $(ma t hbb Z / p^{k} ma t hbb Z)^{*}$ の構造

定理 7.

奇素数

p

と正整数

k

に対して

(Z / p^{k} Z)^{*}

は位数

φ (p^{k}) = p^{k - 1} (p - 1)

の巡回群である．すなわち原始根が存在する．

注意 8.

p = 2

の場合は異なる：

(Z /2 Z)^{*} ≅ {1}

，

(Z /4 Z)^{*} ≅ Z /2 Z

，

k \geq 3

のとき

(Z / 2^{k} Z)^{*} ≅ Z /2 Z \times Z / 2^{k - 2} Z

（巡回群でない）．

5 離散対数問題

定義 9 (離散対数問題（DLP）).

g

を素数

p

の原始根，

h \in (Z / p Z)^{*}

とする．

g^{x} \equiv h (mod p)

を満たす

x

を求める問題を離散対数問題（Discrete Logarithm Problem）という．

注意 10.

DLP は計算困難と信じられており，Diffie-Hellman 鍵共有や ElGamal 暗号の安全性の根拠となっている．最も効率的な古典アルゴリズムは数体篩法で

exp (O ((lo g p)^{1/3} (lo g lo g p)^{2/3}))

の計算量を持つ．Baby-step Giant-step 法は

O (p)

の計算量で DLP を解く一般的手法である．

整数論代数学教科書原始根離散対数

Folio公式

数学の「教科書が書かない行間」をLaTeXで．Folio公式アカウントです．

0 followers·105 articles

原始根と離散対数 ― 巡回群としての $(\mathbb{Z}/p\mathbb{Z})^*$

1 原始根の定義

2 $(ma t hbb Z / p ma t hbb Z)^{*}$ が巡回群であること

3 指数（離散対数）

4 $(ma t hbb Z / p^{k} ma t hbb Z)^{*}$ の構造

5 離散対数問題

Share your expertise with the world

More from Folio公式

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ

1 原始根の定義

2 (mathbbZ/pmathbbZ)∗が巡回群であること

3 指数（離散対数）

4 (mathbbZ/pkmathbbZ)∗の構造

5 離散対数問題

Share your expertise with the world

More from Folio公式

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ

2 $(ma t hbb Z / p ma t hbb Z)^{*}$ が巡回群であること

4 $(ma t hbb Z / p^{k} ma t hbb Z)^{*}$ の構造