5. 원시근과 이산로그

Posted by Bitssam
2015. 7. 18. 09:58 전공수학/Number Theory
V. 원시근과 이산로그

$${x^9} = 5$$


 위 식의 해를 어떻게 표시할 것 인가?

이와 같이 고차의 방정식을 푼다는 것은 쉽지 않다. 이와 같이 고차의 수를 어떻게 다룰지에 대한 고민은 로그의 발명으로 이어졌다. 로그는 다음과 같이 아주 간단하게 결과를 제시해 준다.


${x^9} = 5$

$\Leftrightarrow {\log _2}{x^9} = {\log _2}5$

$\Leftrightarrow 9{\log _2}x = {\log _2}5$

$\Leftrightarrow {\log _2}x = \frac{1}{9}{\log _2}5$

$\Leftrightarrow x = {2^{\frac{1}{9}{{\log }_2}5}}$


 이를 합동식에도 적용할수는 없는가? 당연히 가능하다. 합동식에서의 로그를 이산로그라고한다. 그러나 이산로그를 정의하기 위해서는 이산로그의 존재조건을 명확히 해주어야 한다. 실함수에서는 로그의 존재조건은 밑조건 ($a>0, a \ne 1$)이었다. 이와 상응하듯이 합동식에서도 이산로그의 존재조건이 있는데 이를 원시근이라고 한다. 이제 좀 더 자세히 알아보도록 하자.



1. 위수 


${a^k} \equiv 1$ 인 정수 k는 존재하는가? 우리는 (a, m)=1이라면 k가 반드시 존재함을 오일러정리를 통하여 알아보았다. 

$${a^{\phi (m)}} \equiv 1 \; (mod \; m)$$ 


${a^k} \equiv 1$ 인 정수 k 중 가장 작은 값이 반드시 $\phi (m)$인 것은 아니다. 예를들어, m=7 , a=2에 대해서 k의 최솟값은 3이고 $\phi (m) = 7 - 1 = 6$이다. 우리는 k의 최솟값을 법 m에 관한 a의 위수로정의할것이다.


 $m \ge 2$일 때, $a \in U(Z_m)$에 대하여

${{\mathop{\rm ord}\nolimits} _m}a: = \left| { < a > } \right|$

            $= \min \left\{ {r \in {Z^ + }| \, {a^r} \equiv 1 \, (mod \; m)} \right\}$



물론 서로 합동인 수에 대하여 위수도 같다. 그리고 1과 합동인 수의 위수는 1이다. 모두 정의에 근거한 정리이다.


그 외에도 위수의 성질로 몇가지를 더 들 수 있는데 이들 모두도 충분히 예상할 수 있는 결과이다.


${{\mathop{\rm ord}\nolimits} _m}a = r$에 대하여

 (1) ${a^k} \equiv 1 \Leftrightarrow r|k$

 (2) $r | \phi (m)$

 (3) ${a^k} \equiv {a^l} \; (mod \; m) \Leftrightarrow k \equiv l \; (mod \; r)$

 (4) $\left\{ {{a^1}, \; {a^2}, \; \cdots , \; {a^r}} \right\}$의 두 원소는 법 m에 대하여 합동이 아니다.


거듭제곱의 위수는 다음 정리를 통해 쉽게 계산가능하다.


${{\mathop{\rm ord}\nolimits} _m}a = r$에 대하여

 (1)${{\mathop{\rm ord}\nolimits} _m}{a^k} = \frac{r}{{(k,r)}}$ (거듭제곱의 위수는 지수와 법의 최대공약수를 나눈것이다.)

 (2)${{\mathop{\rm ord}\nolimits} _m}{a^k} = r \Leftrightarrow (k,r)=1$

 (3)$\left\{ {{a^1}, \; {a^2}, \; \cdots , \; {a^r}} \right\}$에서 위수가 r인 원소의 개수 = $\phi (r)$

(1)이 성립하는 이유는 구하고자 하는 위수를 $l$ 이라고 했을 때, ${({a^k})^l} \equiv 1$ (mod m)이 되어야 하므로 $kl \equiv 0$ (mod r)이 된다. 여기서 k를 약분하면 $l \equiv 0$ (mod $\frac{r}{{(k,r)}}$)이 된다.

(2)와 (3)은 (1)에 의해서 자명한 사실이다.


또한 두 수의 곱의 위수에 대해서는 다음과 같은 정리가 존재한다.


 $m \ge 2$, $a,b \in U({Z_m})$ 일 때, 

${{\mathop{\rm ord}\nolimits} _m}a = r$

${{\mathop{\rm ord}\nolimits} _m}b = s$


(1) $(r,s)=1 \Rightarrow {{\mathop{\rm ord}\nolimits} _m}ab = rs$

(2) $ab \equiv 1$ (mod m) $\Rightarrow r=s$ (역원끼리는 위수가 같다)


참고로 밑을 곱해버리면 위수는 각각의 곱하기전 위수의 최소공배수가 된다. (법 m,n에 대해서 각각 거듭제곱이 모두 1이 되려면 최소공배수만큼 제곱되어야 한다는 사실은 자명하다.)



2. 원시근


필요한 위수에 대한 개념을 채웠으니 이산로그의 정의에 필요한 원시근이라는 조건에 대해 알아보자. 원시근이란 기약잉여계의 원소중에 위수가 기약잉여계의 위수와 같은 것들을 말한다. 원시근은 기약잉여계를 생성한다.


 $m \ge 2$, $a,b \in U({Z_m})$ 일 때,

a : 법 m에 관한 원시근

$\Leftrightarrow {{\mathop{\rm ord}\nolimits} _m}a = \phi (m)$

$\Leftrightarrow <a> = U(Z_m)$


이러한 원시근의 정의에 의해 자명한 몇가지 성질들이 있다.


(1) 원시근의 거듭제곱이 1이라면 그 지수는 반드시 $\phi (m)$의 배수다. (기약잉여계의 위수가 위수이므로)

(2) 원시근의 거듭게곱이 만약 같다면 지수끼리 $\phi (m)$을 법으로 합동이다. ((1)과 똑같은 이유이다.)

(3) 원시근은 기약잉여계를 생성한다 (거듭제곱들이 기약잉여계의 원소)

(4) 원시근의 거듭제곱의 위수는  $\frac{\phi (m)}{{(k, \phi (m) )}}$ 이다. (거듭제곱의 위수의 성질에 따라)

(5) 원시근의 거듭제곱이 원시근인것은  $(k, \phi (m))=1$ 과 동치이다.

(6) 원시근의 개수를 따지면 $\phi ( \phi (m) )$ 이다. (기약잉여계의 위수와 서로소인 원소의 모임)


이제 원시근과 관련된 중요한 결과를 소개해야 할 것이다. 결과를 기억하자.


법m에 관한 원시근이 존재할 조건은 법m이 $2, 4, p^k, 2p^k$ 인 경우밖에 없다. 


3. 이산로그


위수와 원시근을 정의하였으니 드디어 이산로그를 정의할 수 있게 되었다. 

이산로그란 합동식에서의 로그로서 다음과 같이 정의한다.


${{\mathop{\rm ind}\nolimits} _r}:U({Z_m}) \to Z, \; {{\mathop{\rm ind}\nolimits} _r}x = y \Leftrightarrow {r^y} \equiv x$ (mod m)


이산로그라는 함수가 잘 정의되기 위해서는 정의역이 기약잉여계이기 때문에 밑이 원시근이어야 원시근의 거듭제곱이 기약잉여계가 되므로 원시근이 밑이 될 수 밖에 없다. 즉, 원시근은 이산로그의 밑조건이 된다.


종합해보면 이산로그를 좀 더 깔끔하게 정의할 수 있다.


g : 법 m에 관한 원시근일 때

${{\mathop{\rm ind}\nolimits} _g}:U({Z_m}) \to Z$

${{\mathop{\rm ind}\nolimits} _g}a$ = min{$y \in Z_0^+ | g^y \equiv a$ (mod m)}


이산로그의 연산도 실함수로그의 연산과 같다. 다만 $\phi (m)$을 법으로 같다.

다만 1이 아닌 역원의 이산로그를 서로 더하면 그 값은 $\phi (m)$이다. 그 이유는 $\phi (m)$를 법으로 하지만 둘다 0보다 크기 때문에 더해서 0은 아니고 2$\phi (m)$을 넘지는 않을것이기 때문이다.


이산로그에서도 원시근의 동치조건을 발견할 수 있다. 원시근의 거듭제곱이 원시근인것은  $(k, \phi (m))=1$ 과 동치이다. 라는 정리에서 k를 이산로그로 표현해주면 된다. $h=g^k$로 두면 k를 g를 밑으로 하는 이산로그로 표현할 수 있으므로 다음과 같은 정리를 얻는다.


기약잉여계의 원소 h가 원시근인것은  $({{\mathop{\rm ind}\nolimits} _g}h, \phi (m))=1$ 과 동치이다.


밑변환공식도 실함수로그와 비슷하다.


${{\mathop{\rm ind}\nolimits} _h}a \equiv {{\mathop{\rm ind}\nolimits} _h}g \cdot {{\mathop{\rm ind}\nolimits} _g}a$ (mod $\phi$(m))

${{\mathop{\rm ind}\nolimits} _h}g \cdot {{\mathop{\rm ind}\nolimits} _g}h \equiv {{\mathop{\rm ind}\nolimits} _h}h \equiv 1$ (mod $\phi$(m))

$gh \equiv 1$ (mod m) $ \Rightarrow {{\mathop{\rm ind}\nolimits} _g}a + {{\mathop{\rm ind}\nolimits} _h}a = \phi (m)$









'전공수학 > Number Theory' 카테고리의 다른 글

7. 방정식의 풀이 (종합편)  (0) 2015.07.18
6. 이차잉여 (르장드르기호, 야코비기호)  (2) 2015.07.18
5. 원시근과 이산로그  (0) 2015.07.18
4. 페르마소정리, 오일러정리  (0) 2015.07.18
3. 합동식  (0) 2015.07.18
2. 소수와 소인수분해  (0) 2015.07.17