2.4 원시근과 순환군 (Primitive Roots)

원시근은 모듈러 군 $(\mathbb{Z}/n\mathbb{Z})^\times$의 모든 원소를 자신의 거듭제곱으로 생성할 수 있는 특별한 원소입니다. 이는 이산 로그(Discrete Logarithm) 문제의 기초가 됩니다.

1. 위수(Order)와 원시근의 정의

$\gcd(a, n)=1$일 때, $a^k \equiv 1 \pmod n$을 만족하는 최소의 양의 정수 $k$를 법 $n$에 대한 $a$의 위수라 하고 $\text{ord}_n(a)$로 표기합니다.

Primitive Root Definition

어떤 정수 $g$의 위수가 $\phi(n)$과 정확히 일치할 때, $g$를 법 $n$에 대한 원시근이라 합니다.

$$\text{ord}_n(g) = \phi(n)$$

2. 원시근이 존재할 조건

모든 정수 $n$에 대해 원시근이 존재하는 것은 아닙니다. 오직 다음의 형태에서만 원시근이 존재합니다.

$n = 2, 4$
$n = p^k$ ($p$는 홀수인 소수, $k \ge 1$)
$n = 2p^k$ ($p$는 홀수인 소수, $k \ge 1$)

이 경우 곱셈군 $(\mathbb{Z}/n\mathbb{Z})^\times$는 순환군(Cyclic Group) $C_{\phi(n)}$과 동형입니다.

3. 원시근의 개수와 성질

법 $n$에 원시근이 존재한다면, 그 개수는 정확히 $\phi(\phi(n))$개입니다.
$g$가 원시근이면, $g^k$가 원시근일 필요충분조건은 $\gcd(k, \phi(n)) = 1$인 것입니다.
라그랑주 정리: 소수 $p$에 대해 법 $p$인 $n$차 합동식은 최대 $n$개의 해를 갖습니다. 이로부터 모든 소수 $p$에 대해 원시근이 존재함이 유도됩니다.

4. 이산 로그 (Discrete Logarithm)

원시근 $g$가 주어졌을 때, 임의의 $a \in (\mathbb{Z}/n\mathbb{Z})^\times$에 대해 $g^x \equiv a \pmod n$을 만족하는 $x$를 찾는 문제입니다. 실수가 아닌 모듈러 세계의 로그이며, 현대 암호(Diffie-Hellman 등)의 안전성을 보장하는 난제입니다.