1. 개요
原始根, primitive root정수론, 특히
합동식에서의 개념으로, 어떤
기약잉여계의 모든 원소를 원시근의 거듭제곱으로 표현할 수 있을 때 이를 원시근이라 한다.
아래의 원시근을 이용한 암호 알고리즘으로 인해 나름의 실용적인 쓰임새도 있다.
2. 정의
원시근을 정의하기에 앞서 어떤 원소의 위수를 정의할 필요가 있다.
'''위수(order)'''[1] 일반적으로 군론에서의 원소의 위수(order)의 정의도 위와 사실상 동일하다. 이 위수는 어찌 보면 곱셈에 대한 위수이기 때문에 명확한 표현을 위해서 multiplicative order라고도 쓰기도 한다. 애초에 order가 워낙 많이 나오는 말이기도 하고. '계수' 등으로도 번역되기도 한다. (David M. Burton, 이준복/이중섭 공역, 《기초정수론》, 경문사 등)
-
$$ {\rm gcd}(a,n)=1 $$인 어떤 정수 $$a$$가 법 $$ n $$에 대해 $$k$$의 위수를 가진다 함은, $$ k $$ 가 $$a^k\equiv 1\left(\text{mod}\,n\right)$$ 을 만족하는 최소의 양의 정수일 때이다.
|
쉽게 말해 어떤 정수를 계속 거듭제곱해서 주어진 잉여계의 1이 되는 자연수가 있는데 그것이 되는 최소의 정수를 위수 또는 계수라고 한다.
오일러 정리에 의해 어떤 수에 대해서도 위수가 존재하며 $$\varphi(n)$$ 이하여야만 함을 알 수 있고, 좀더 생각하면 모든 위수는 $$\varphi(n)$$의 약수가 되어야 한다는 것도 증명할 수 있다. 이 위수가 정확히 $$\varphi(n)$$이 되는 원소가 바로 원시근이다.
'''원시근(primitve root)'''
--
만일 $$ {\rm gcd}(a,n)=1 $$ 인 정수 $$ a $$ 에 대해 $$ a $$가 법 $$n$$에 대한 기약잉여계에서 $$ {\varphi\left(n\right)} $$ 의 위수를 가질 때 $$ a $$를 '''법 $$\boldsymbol{n}$$에 대한 원시근'''(primitive root modulo n)이라 한다.
|
정수론의 개념이 그렇듯이 추상대수학의 언어에 익숙하다면 다음처럼 정의할 수도 있다.
주어진 정수 몫환 $$ \mathbb{Z}/n\mathbb{Z}$$ 의 단위원(unit)의 모임$$\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}$$ 이 순환군(cyclic group)일 때 그 생성원(generator)을 법 $$n$$에 대한 원시근이라 한다.
|
3. 존재성과 찾는 법
일단 원시근은 찾으면 상당히 편리한 도구가 되지만 주어진 잉여계에 항상 원시근이 존재하리라는 보장은 없다. 하지만 원시근이 존재할 필요충분조건을 이미 알고 있는데 잉여계가 $$n=2 $$, $$4 $$, $$p^k $$, $$2p^k $$꼴일 때에만 원시근이 존재한다.
[2] 일반적으로 다음이 성립한다.
법 $$n$$에 대한 기약잉여계의 곱셈군 $$(\mathbb{Z}/n)^{\times}$$의 구조는 다음처럼 주어진다.
* $$n=2$$이면 $$(\mathbb{Z}/n)^{\times} \simeq 1$$이다.
* $$n=2^k$$이고 $$k \ge 2$$이면 $$ (\mathbb{Z}/n)^{\times} \simeq \mathbb{Z}/2^{k-2} \times \mathbb{Z}/2$$이다.
* $$n=p^k$$이면 ($$p$$: 홀수인 소수) $$ (\mathbb{Z}/n)^{\times} \simeq \mathbb{Z}/p^{k-1}(p-1)$$이다.
* $$n$$이 서로 다른 소수들의 곱 $$\prod {p_i}^{e_i}$$ 꼴이면, 중국인의 나머지 정리에 의해 $$(\mathbb{Z}/n)^{\times} \simeq \prod (\mathbb{Z}/{p_i}^{e_i})^{\times}$$ 꼴로 분해되고, 위의 경우들로부터 답을 알 수 있다.
|
이 사실에 따르면 $$(\mathbb{Z}/n)^{\times}$$이 순환군인 경우는 $$n=2 $$, $$4 $$, $$p^k $$, $$2p^k $$가 전부라는 것을 확인할 수 있다.
- [대략적인 증명 과정]
- $$n=2,4$$: 이정도는 손으로 해보자.
- $$n=2^k$$, $$k \ge 3$$: 우선 5의 위수가 $$2^{k-2}$$임을 증명한다. $$ (1+2^2)^{2^{k-3}} \simeq 1+2^{k-1} (\mathrm{mod}~2^{k})$$을 보이면 되는데, $$(1+2^{k-1}+a 2^k)^2 \simeq 1 + 2^k (\mathrm{mod}~2^{k+1})$$을 이용하면 수학적귀납법으로 어렵지 않게 가능하다. 따라서 정확히 $$2^{k-2}$$개 있는 $$4k+1$$꼴 수들의 모음은 모두 5의 제곱꼴이다. 한편 $$2^{k-1}-1$$의 위수는 2이고 (제곱해서 이항정리로 바로 확인) 이 $$4k-1$$꼴 수는 5의 제곱꼴로 나타낼 수 없다. 이를 종합하면 $$C_2 \times C_{2^{k-2}} \rightarrow (\mathbb{Z}/n)^{\times}$$에서 $$C_2$$의 생성원을 $$2^{k-1}-1$$로, $$C_{2^{k-2}}$$의 생성원을 5로 보내면 동형사상이 됨을 체크할 수 있다.
- $$n=p$$: 사실상 가장 어려운 경우이다. 공통된 스텝은 $$d \vert p-1$$이면 $$x^d \equiv 1(\mathrm{mod}~n)$$은 정확히 $$d$$개의 해를 가짐을 보이는 것인데, $$x^{p-1}-1 = (x^d - 1) f(x)$$꼴로 나타내었을 때 좌변은 법 $$p$$로 $$(x-1)(x-2)\cdots(x-p+1)$$로 인수분해되므로 우변의 다항식도 서로 다른 일차인수들로 인수분해되어야 하므로 된다.
여기서부터 방법이 나뉘는데, 만약
현대대수학 특히 유한생성 아벨군의 분류정리를 배웠다면, 군이 순환군으로 안 떴을 경우에는 군의 위수 $$p-1$$보다 작은 수(정확히는 최대의 invariant factor) $$a$$가 있어 $$x^a \equiv 1$$이 $$p-1>a$$개의 해를 가지므로 모순이 된다는 것을 바로 캐치할 수 있다. 이걸 사용할 수 없는 대부분의 정수론 교재에서는 좀더 돌아가야 한다. 보통 $$x^d \equiv 1$$의 해들은 사실 위수가 $$d$$의 약수가 되는 성질임을 관찰해 위수가 정확히 $$d$$개인 것이 $$\varphi(d)$$라는 것을 항등식 $$\sum_{e \vert d} \varphi(e) = d$$을 이용해 수학적귀납법으로 보이게 된다.
- $$n=p^k$$, $$k \ge 2$$: 우선 이항정리를 활용해 $$1+p$$의 위수가 $$p^{k-1}$$임을 보인다. 수학적 귀납법으로 $$(1+p)^{p^{k-2}} \equiv 1 + p^{k-1} (\mathrm{mod}~p^k)$$을 보이면 된다. 그 다음으로는 방정식 $$x^{p-1}-1=0$$의 해들이 헨젤 리프팅(Hensel lifting)이 가능하다는 것을 이용해 위수가 $$p-1$$인 원소가 존재함을 보인다. 마지막으로는 '$$a,b$$의 위수가 각각 $$d,e$$고 서로소이면 $$ab$$의 위수는 $$de$$이다'를 증명해 원시근을 찾을 수 있다. 원시근 자체는 헨젤 리프팅이 되지 않는데, 이는 방정식 $$x^{p^{k-2}(p-1)}-1 \equiv 0$$의 성질이 매우 좋지 않은 까닭이다(ramified).
- $$n=p^k$$, $$k \ge 2$$: 우선 이항정리를 활용해 $$1+p$$의 위수가 $$p^{k-1}$$임을 보인다. 수학적 귀납법으로 $$(1+p)^{p^{k-2}} \equiv 1 + p^{k-1} (\mathrm{mod}~p^k)$$을 보이면 된다. 그 다음으로는 방정식 $$x^{p-1}-1=0$$의 해들이 헨젤 리프팅(Hensel lifting)이 가능하다는 것을 이용해 위수가 $$p-1$$인 원소가 존재함을 보인다. 마지막으로는 '$$a,b$$의 위수가 각각 $$d,e$$고 서로소이면 $$ab$$의 위수는 $$de$$이다'를 증명해 원시근을 찾을 수 있다. 원시근 자체는 헨젤 리프팅이 되지 않는데, 이는 방정식 $$x^{p^{k-2}(p-1)}-1 \equiv 0$$의 성질이 매우 좋지 않은 까닭이다(ramified).}}}
하지만 원시근이 존재한다고 해서 그게 바로 툭 튀어나오는것이 아닌지라 어떤 잉여계의 최초의 원시근은 반드시 계산으로 찾아야 한다. 그래도 하나의 원시근만 찾으면 나머지 원시근을 찾는것은 생각보다 간단한데 어떤 원시근 $$ a $$ 에 대해 다른 원시근은 $$ a^k ({\rm gcd}(k,{\varphi\left(n\right)})=1) $$ 의 형태로 나타나기 때문이다. 저 방법을 이용하여 원시근이 존재하는 잉여계의 원시근은 총 $$\varphi(\varphi(n))$$ 개가 존재함도 알 수 있다. 아래의 이산로그 문제로 인해서 소수 $$p$$에 대한 원시근을 빠르게 찾는 게 중요해졌고, 따라서 많은 알고리즘이 연구되었지만 ($$\log n$$에 대한) 다항복잡도 해법은 아직 나오지 않고 있다.
4. 원시근과 이산 로그
이제 원시근이 있으면 이 원시근으로부터 이산로그(discrete logarithm) 혹은 지수(index)를 정의할 수 있다. 우리가 실수에 대한 로그를 지수함수의 역함수로 정의했듯이, 원시근 $$g$$가 존재하면 다음처럼 정의하는 함수 $$ f : \mathbb{Z}/{\varphi(n)} \rightarrow \left(\mathbb{Z}/n \right)^{\times} $$, $$ f(n) \mapsto g^n $$가 전단사가 됨을 알 수 있는데 이때 이 역함수$$f^{-1}$$를 이산로그라 한다. 보통 $$k = \mathrm{ind}_g m $$ 처럼 표기한다. ($$m \equiv g^k(\mathrm{mod}~n)$$)
어떤 수의 이산로그를 빠르게 찾는 것은 현재까지는 어려운 문제로, ($$\log n$$에 대한) 다항복잡도 해법이 아직은 없다. 덕분에 이산로그 문제를 활용한 수많은 공개키
암호 알고리즘인 엘가멜(Elgamel) 복호화,
디피-헬만 키 교환 등등이 있으며, 이들은 당연히 이산로그 문제가 풀리는 순간 구식이 될 것이다.
5. 체론에서의 원시근
일반적인
체에서도 비슷하게 곱셈에 대한 위수를 생각할 수 있고, 이러한 맥락에서 방정식 $$x^n=1$$의 해들 중 곱셈에 대한 위수가 정확히 $$n$$이 되는 것을 원시근이라 부르기도 한다. '위수 $$n$$의 원시근' (primitive root of order n) 이런 식으로 부른다. 예시를 들자면
복소수에서는 위수 4짜리 원시근은 $$i$$, $$-i$$ 2개가 있고, 위수 3짜리 원시근은 $$\displaystyle {(-1 \pm \sqrt{3}i)}/{2}$$ 이렇게 2개가 있을 것이다. 임의의 체에서 $$x^n=1$$의 해들로 확장을 취하면(즉 $$x^n-1$$의 분해체(splitting field)를 생각하면), $$x^n=1$$의 해들의 곱셈군은 $$\mathbb{Z}/n$$과 동형이라는 사실을 증명할 수 있으므로(증명방식은 소수법에 대해 원시근이 존재한다는 증명과 매우 비슷하다.), 위수 $$n$$의 원시근은 확장체에서 $$\varphi(n)$$개가 항상 존재한다는 사실을 알 수 있다.
유한체(finite field)의 경우 $$\mathbb{F}_{q}^{\times}$$는 항상 순환군임을 보일 수 있으므로, 이 순환군의 생성원을 원시근이라 부르기도 한다. 특수한 경우로 $$q=p$$일 때가 정수론의 원시근이랑 일치하게 된다.