원시근(Primitive Roots)

정의
- 원시근
  - 원시근 예제
- 이산로그
  - 이산로그 예제
참고문헌

정의

원시근

Primitive Roots

A primitive root modulo a prime $p$ is an integer $r$ in $Z_p$ such that every nonzero element of $Z_p$ is a power of $r$ .

원시근 모듈로 소수 $p$ 는 $Z_{p}$ 의 원소이며, 정수이다.
- $Z_p$ 는 $r$ 의 거듭제곱으로 이루어진 0 이 아닌 정수들이다.

모든 소수 $p$ 에 대해 원시근 모듈로 $p$ 가 존재한다.

만약 $a$ 가 $Z_{p}$ 의 원소이면 (즉, $0 < a \leq p - 1$ 이면)
- $Z_p$ 에 $r^e = a$ 인 유일한 지수 $e$ 가 있다. (즉, $r^e \bmod p = a$ 인 $e$ 가 있다.)

원시근 예제

2 와 3 이 원시근 모듈로 11 임을 결정하라.

$Z_{11}$ 안에서 2의 거듭제곱을 계산해보자. 각 거듭제곱의 결과를 11로 나눈 나머지를 구하면 된다.

\begin{aligned} 2^{1} & = 2 \\ 2^{2} & = 4 \\ 2^{3} & = 8 \\ 2^{4} & = 5 \\ 2^{5} & = 10 \\ 2^{6} & = 9 \\ 2^{7} & = 7 \\ 2^{8} & = 3 \\ 2^{9} & = 6 \\ 2^{10} & = 1 \end{aligned}

$\begin{align} 2^1 & = 2 \\ 2^2 & = 4 \\ 2^3 & = 8 \\ 2^4 & = 5 \\ 2^5 & = 10 \\ 2^6 & = 9 \\ 2^7 & = 7 \\ 2^8 & = 3 \\ 2^9 & = 6 \\ 2^{10} & = 1 \\ \end{align}$

1 부터 10 까지 다 있다.

$Z_{11}$ 의 모든 원소가 2의 거듭제곱이므로 2 는 11의 원시근이다.

이번에는 3 이 11 의 원시근인지 알아보자.

\begin{aligned} 3^{1} & = 3 \\ 3^{2} & = 9 \\ 3^{3} & = 5 \\ 3^{4} & = 4 \\ 3^{5} & = 1 \\ 3^{6} & = 3 \\ 3^{7} & = 9 \\ 3^{8} & = 5 \\ 3^{9} & = 4 \\ 3^{10} & = 1 \end{aligned}

$\begin{align} 3^1 & = 3 \\ 3^2 & = 9 \\ 3^3 & = 5 \\ 3^4 & = 4 \\ 3^5 & = 1 \\ 3^6 & = 3 \\ 3^7 & = 9 \\ 3^8 & = 5 \\ 3^9 & = 4 \\ 3^{10} & = 1 \\ \end{align}$

$3, 9, 5, 4, 1$ 이 반복된다.

$2, 6, 7, 8, 10$ 이 빠졌으므로 3 은 11 의 원시근이 아니다.

이산로그

discrete logarithm

Suppose that $p$ is a prime, $r$ is a primitive root modulo $p$ , and $a$ is an integer between 1 and $p − 1$ inclusive. If $r^e \bmod p = a$ and $0 ≤ e ≤ p − 1$ , we say that $e$ is the discrete logarithm of $a$ modulo $p$ to the base $r$ and we write $\log_r a = e$ (where the prime $p$ is understood).

$p$ 가 소수이고, $r$ 이 원시근 모듈로 $p$ 이고, $a$ 가 $1 \leq a \leq p - 1$ 인 정수라 하자.
- $r^e \bmod p = a$ 이고, $0 \le e \le p-1$ 이면…
- $e$ 를 $r$ 을 밑으로 하는 $a$ 모듈로 $p$ 의 이산로그라 한다.
  - 표기는 $\log_r a = e$ 이다.

이산로그 문제는 쉬워 보이지만, 의외로 다항시간 알고리즘이 존재하지 않는다.

이산로그 문제의 어려움은 암호학에서 유용하게 쓰인다.

이산로그 예제

2를 밑으로 하는 3과 5의 모듈로 11의 이산로그를 찾아라.

위의 원시근 예제를 풀 때 다음을 미리 계산해 두었었다.

\begin{aligned} 2^{4} & = 5 \\ 2^{8} & = 3 \end{aligned}

$\begin{align} 2^4 & = 5 \\ 2^8 & = 3 \\ \end{align}$

따라서 3 과 5는 $Z_{11}$ 에 들어있다.

$2^4 \bmod 11 = 5$ 이고, $0 \le 4 \le 10$ 이므로 2 를 밑으로 하는 5 모듈로 11 의 이산로그는 4 이다.

막상 써보면 평범한 로그와 똑같이 생겼으므로 어렵지 않게 이해할 수 있다.

\log_{2} 5 = 4

$\log_2 5 = 4$

한편, $2^8 \bmod 11 = 3$ 이고, $0 \le 8 \le 10$ 이므로 2 를 밑으로 하는 3 모듈로 11 의 이산로그는 8 이다.

\log_{2} 3 = 8

$\log_2 3 = 8$

참고문헌

Rosen의 이산수학 / Kenneth H. Rosen 저 / 공은배 등저 / 한국맥그로힐(McGraw-Hill KOREA) / 2017년 01월 06일