原始根, primitive root

정수론, 특히 합동식에서의 개념으로, 어떤 기약잉여계의 모든 원소를 원시근의 거듭제곱으로 표현할 수 있을 때 이를 원시근이라 한다.
아래의 원시근을 이용한 암호 알고리즘으로 인해 나름의 실용적인 쓰임새도 있다.

원시근을 정의하기에 앞서 어떤 원소의 위수를 정의할 필요가 있다.

쉽게 말해 어떤 정수를 계속 거듭제곱해서 주어진 잉여계의 1이 되는 자연수가 있는데 그것이 되는 최소의 정수를 위수 또는 계수라고 한다. 오일러 정리에 의해 어떤 수에 대해서도 위수가 존재하며 [math(varphi(n))] 이하여야만 함을 알 수 있고, 좀더 생각하면 모든 위수는 [math(varphi(n))]의 약수가 되어야 한다는 것도 증명할 수 있다. 이 위수가 정확히 [math(varphi(n))]이 되는 원소가 바로 원시근이다.

정수론의 개념이 그렇듯이 추상대수학의 언어에 익숙하다면 다음처럼 정의할 수도 있다.

일단 원시근은 찾으면 상당히 편리한 도구가 되지만 주어진 잉여계에 항상 원시근이 존재하리라는 보장은 없다. 하지만 원시근이 존재할 필요충분조건을 이미 알고 있는데 잉여계가 [math(n=2 )], [math(4 )], [math(p^k )], [math(2p^k )]꼴일 때에만 원시근이 존재한다.[3]는 홀수인 소수이다] 일반적으로 다음이 성립한다.

이 사실에 따르면 [math((mathbb{Z}/n)^{times})]이 순환군인 경우는 [math(n=2 )], [math(4 )], [math(p^k )], [math(2p^k )]가 전부라는 것을 확인할 수 있다.

[대략적인 증명 과정]

• [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( a )] 에 대해 다른 원시근은 [math( a^k ({rm gcd}(k,{varphileft(nright)})=1) )] 의 형태로 나타나기 때문이다. 저 방법을 이용하여 원시근이 존재하는 잉여계의 원시근은 총 [math(varphi(varphi(n)))] 개가 존재함도 알 수 있다. 아래의 이산로그 문제로 인해서 소수 [math(p)]에 대한 원시근을 빠르게 찾는 게 중요해졌고, 따라서 많은 알고리즘이 연구되었지만 ([math(log 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)]일 때가 정수론의 원시근이랑 일치하게 된다.