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