[목차] == 개요 == {{{+1 [[原]][[始]][[根]], primitive root}}} [[정수론]], 특히 [[합동식]]에서의 개념으로, 어떤 [[기약잉여계]]의 모든 원소를 원시근의 거듭제곱으로 표현할 수 있을 때 이를 원시근이라 한다. 아래의 원시근을 이용한 암호 알고리즘으로 인해 나름의 실용적인 쓰임새도 있다. == 정의 == 원시근을 정의하기에 앞서 어떤 원소의 위수를 정의할 필요가 있다. ||'''위수(order)'''[* 일반적으로 군론에서의 원소의 위수(order)의 정의도 위와 사실상 동일하다. 이 위수는 어찌 보면 곱셈에 대한 위수이기 때문에 명확한 표현을 위해서 multiplicative order라고도 쓰기도 한다. 애초에 order가 워낙 많이 나오는 말이기도 하고. '계수' 등으로도 번역되기도 한다. (__David M. Burton, 이준복/이중섭 공역, 《기초정수론》, 경문사__ 등)] ----- [math( {\rm gcd}(a,n)=1 )]인 어떤 정수 [math(a)]가 법 [math( n )]에 대해 [math(k)]의 위수를 가진다 함은, [math( k )] 가 [math(a^k\equiv 1\left(\text{mod}\,n\right))] 을 만족하는 최소의 양의 정수일 때이다.|| 쉽게 말해 어떤 정수를 계속 거듭제곱해서 주어진 잉여계의 1이 되는 자연수가 있는데 그것이 되는 최소의 정수를 위수 또는 계수라고 한다. [[오일러 정리]]에 의해 어떤 수에 대해서도 위수가 존재하며 [math(\varphi(n))] 이하여야만 함을 알 수 있고, 좀더 생각하면 모든 위수는 [math(\varphi(n))]의 약수가 되어야 한다는 것도 증명할 수 있다. 이 위수가 정확히 [math(\varphi(n))]이 되는 원소가 바로 원시근이다. ||
'''원시근(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)]에 대한 원시근이라 한다.|| == 존재성과 찾는 법 == 일단 원시근은 찾으면 상당히 편리한 도구가 되지만 주어진 잉여계에 항상 원시근이 존재하리라는 보장은 없다. 하지만 원시근이 존재할 필요충분조건을 이미 알고 있는데 잉여계가 [math(n=2 )], [math(4 )], [math(p^k )], [math(2p^k )]꼴일 때에만 원시근이 존재한다.[* [math(p)]는 홀수인 소수이다] 일반적으로 다음이 성립한다. ||
법 [math(n)]에 대한 기약잉여계의 곱셈군 [math((\mathbb{Z}/n)^{\times})]의 구조는 다음처럼 주어진다. * [math(n=2)]이면 [math((\mathbb{Z}/n)^{\times} \simeq 1)]이다. * [math(n=2^k)]이고 [math(k \ge 2)]이면 [math( (\mathbb{Z}/n)^{\times} \simeq \mathbb{Z}/2^{k-2} \times \mathbb{Z}/2)]이다. * [math(n=p^k)]이면 ([math(p)]: 홀수인 소수) [math( (\mathbb{Z}/n)^{\times} \simeq \mathbb{Z}/p^{k-1}(p-1))]이다. * [math(n)]이 서로 다른 소수들의 곱 [math(\prod {p_i}^{e_i})] 꼴이면, [[중국인의 나머지 정리]]에 의해 [math((\mathbb{Z}/n)^{\times} \simeq \prod (\mathbb{Z}/{p_i}^{e_i})^{\times})] 꼴로 분해되고, 위의 경우들로부터 답을 알 수 있다.|| 대수학적으로 접근하면 [math((\mathbb{Z}/n)^{\times})]이 순환군인 경우는 [math(n=2 )], [math(4 )], [math(p^k )], [math(2p^k )]가 전부라는 것을 확인할 수 있다. {{{#!folding [대략적인 증명 과정] * [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).}}} 하지만 원시근이 존재한다고 해서 그게 바로 툭 튀어나오는것이 아닌지라 어떤 잉여계의 최초의 원시근은 반드시 --노가다--계산으로 찾아야 한다. 아래의 이산로그 문제로 인해서 소수 [math(p)]에 대한 원시근을 빠르게 찾는 게 중요해졌고, 많은 알고리즘이 연구되었지만 ([math(\log n)]에 대한) 다항복잡도 해법은 아직 나오지 않고 있다. 그래도 하나의 원시근 [math( a )]만 찾으면 나머지 원시근은 [math( a^k )] (단, [math({\rm gcd}(k,{\varphi\left(n\right)})=1)])의 형태로 쉽게 구할 수 있다. 따라서 원시근이 존재하는 잉여계의 원시근은 총 [math(\varphi(\varphi(n)))] 개가 존재함도 알 수 있다. == 원시근과 이산 로그 == 이제 원시근이 있으면 이 원시근으로부터 이산로그(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) 복호화, [[디피-헬만 키 교환]] 등등이 있으며, 이들은 당연히 이산로그 문제가 풀리는 순간 구식이 될 것이다. == 체론에서의 원시근 == 일반적인 [[체(대수학)|체]]에서도 비슷하게 곱셈에 대한 위수를 생각할 수 있고, 이러한 맥락에서 방정식 [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)]일 때가 정수론의 원시근이랑 일치하게 된다. == 군론의 위수 == [[군(대수학)|군론]](group theory)에서 일반적으로 위수(Order)는 어떤 군의 유한개의 원소들의 수효라고 정의해 볼때 그 군의 원시근의 갯수를 가리킬수도 있고 그 군의 부분군(순환군,잉여류 등)의 갯수를 가리킬수도 있다. 부분군과 위수의 쓰임새는 [[라그랑주 정리(군론)|라그랑주 정리]]에서 잘 다루어진다. 위수의 기호로는 집합(set)의 크기(size)인 [[카디널리티]](cardinality) 기호인 |G|나 G()등을 같이 사용한다. 하지만 card(G)보다는 ord(G)가 선호된다.[* 전자의 경우 대학교 집합론 교재에서 잠시 다루는 정도이며, 정작 위상수학으로 넘어가면 org(G)도 잘 안 쓰고 |G|를 더 많이 쓴다.] [[분류:정수론]][[분류:대수학]]