이동식 저장소

Complete Residue System $Z_6=\{0,1,2,3,4,5\}$에서, $5\times 5=1\mathrm{mod}6$이므로 $5$의 역원은 $5$이다. 그런데 $2$와 곱해서 $1$이 되는 수, 즉 $2$의 역원은 존재하지 않는다. 따라서 Complete Residue System에서는 곱셈이 잘 정의되지 않는다. 곱셈이 잘 정의되지 않는다는 말은 역원 또는 항등원이 존재하지 않는다는 말과 같다.

우리는 곱셈과 나눗셈이 잘 정의되는 Residue System을 원한다.

Reduced Residue System $Z_m^{\ast }=\{a|gcd(a,m)=1,0\le a<m\}$

$Z_m^{\ast }$에서 곱셈이 잘 정의된다는 것을 증명한다.

$\mathrm{\forall }a\in Z_m^{\ast },\mathrm{\exists }xax=1\mathrm{mod}m$

$gcd(a,m)=1$이므로 유클리드 알고리즘으로부터 $ax+my=1$을 만족하는 정수 $x,y$가 존재한다. 이항하면 $ax=-ym+1$이므로 $ax$를 $m$으로 나눈 나머지가 $1$이다. 즉 $ax=1\mathrm{mod}m$이다. $x$의 값을 정확히 알 수는 없지만 어쨌든 곱셈의 역원이 존재한다.

$(ab)c=a(bc)\mathrm{mod}m$ (곱셈의 결합법칙) 증명

$a=q_{1}m+a_1,b=q_{2}m+b_1,c=q_{3}m+c_1$이라 하면 $(ab)c=((q_{1}m+a_1)(q_{2}m+b_1))(q_{3}m+c_1)=(q_1{q}_2{m}^2+a{q}_{2}m+b{q}_{1}m+a_1{b}_1)(q_{3}m+c_1)$이고, $a(bc)=(q_{1}m+a_1)((q_{2}m+b_1)(q_{3}m+c_1))=(q_{1}m+a_1)(q_2{q}_3{m}^2+b{q}_3+c{q}_{2}m+bc)$이다. 두 식을 전개해서 정리하면 양변이 같음을 알 수 있다. 양변이 같으므로 양변을 $m$으로 나눈 나머지도 같다. 따라서 $(ab)c=a(bc)\mathrm{mod}m$이다.

사실 $Z_m^{\ast }$에서는 덧셈과 뺄셈이 잘 정의되지 않는다.

Real Number System

Residue System이 어색할 수도 있으므로, 실수 집합에서 이야기해 보자.

실수란 무엇인가? 사실 실수라는 말 자체가 정의된 것은 아니다. 대신 실수 집합에서 성립하는 성질을 Axiom, 즉 공리라고 하여 공리가 성립할 때 실수 집합에서 어떤 일이 일어나는지 관찰한다. 

예를 들어 $a,b\in R\to a+b\in R$은 공리이다. $a\in R\to -a\in R$도 공리이다. 이런 공리가 모두 성립한다고 생각하다 보면 더 복잡한 성질을 이끌어낼 수 있다. 

물론 아무거나 다 공리로 놓을 수는 없다. 예를 들어 서로 다른 역원이 2개 존재하는 System은 생각할 수 없다. 역원이 존재한다면 반드시 하나만 존재한다는 사실을 증명할 수 있기 때문이다. "내 시스템에서는 역원이 2개 존재해!"라고 우길 수는 있어도, 그 시스템에서 의미있는 사실을 이끌어낼 수는 없을 것이다.

다시 돌아와서

$m$이 소수일 때 $Z_m^{\ast }$는 어떻게 될까? $1\le i<m$인 모든 $i$에 대해 $gcd(i,m)=1$이므로 $Z_m^{\ast }=\{1,2,3,\cdots ,m-1\}$이다. 즉 $Z_m=Z_m^{\ast }\cup \{0\}$이므로 $Z_m$에서 모든 사칙연산이 잘 정의된다. $0$의 곱셈의 역원은 실수 집합에서도 존재하지 않으므로 생각할 필요가 없다.

소수 $m$의 Residue System은 사칙연산이 잘 정의되므로 매우 유용하다. 조금만 더 공부하면 $Z_m$을 가지고 실제로 암호를 만들 수 있다.

오일러의 정리

$a\in Z_m^{\ast }$에 대해 $a^1,a^2,a^3,\cdots \mathrm{mod}m$는 모두 $Z_m^{\ast }$의 원소이다. $Z_m^{\ast }$는 유한하므로 $a$의 제곱을 계속 계산하다 보면 비둘기집의 원리에 의해 언젠가는 $a^i=a^j\mathrm{mod}m$를 만족한다. $i<j$라 놓으면 $a^i=a^i\times a^{j-i}\mathrm{mod}m$이므로 $1=a^{j-i}\mathrm{mod}m$이다. $Z_m^{\ast }$이 나눗셈에 대해 닫혀있기 때문에 양변을 $a^i$로 나눠도 등식이 성립한다.

그러면 등식이 성립하도록 하는 $i,j$를 구할 수 있을까? 오일러의 정리에서 그 답을 찾을 수 있다.

• $a\in Z_m^{\ast }\to a^{\phi (m)}=1\mathrm{mod}m(\phi (m)=|Z_m^{\ast }|)$

예를 들어 $Z_{15}^{\ast }=\{1,2,4,7,8,11,13,14\}$의 각 원소를 $|Z_{15}^{\ast }|=8$제곱하면 모두 1이 나온다. 물론 $4$제곱만 해도 1이 나오지만, 적어도 $|Z_m^{\ast }|$제곱하면 무조건 1이 나온다는 사실은 분명하다.

증명

$Z_m^{\ast }=\{a_1,a_2,\cdots ,a_k\}$라 하면 $\phi (m)=k$이다. $a=a_i(1\le i\le k)$라 하면 $a{Z}_m^{\ast }=\{a{a}_1,a{a}_2,\cdots ,a{a}_k\}\subset Z_m^{\ast }$이다. $Z_m^{\ast }$이 곱셈에 대해 닫혀있으므로 $a{a}_j\in Z_m^{\ast }$이다. 그런데 $i\ne j$이면 $aai\ne a{a}_j\mathrm{mod}m$이므로 $a{Z}_m^{\ast }$의 모든 원소는 서로 다르고, 따라서 $a{Z}_m^{\ast }=Z_m^{\ast }$이다.

따라서 $a{a}_1\times a{a}_2\times \cdots a{a}_k=a_1\times a_2\times \cdots \times a_k\mathrm{mod}m$이다. 좌변은 $a{Z}_m^{\ast }$의 원소를 모두 곱한 것이고, 우변은 $Z_m^{\ast }$의 원소를 모두 곱한 것이다. 두 집합이 같으므로 두 집합의 모든 원소를 곱해도 같다.

좌변을 정리하면 $a^k\times a_1\times a_2\times \cdots \times a_k=a_1\times a_2\times \cdots a_k\mathrm{mod}m$이고, 따라서 $a^k=1\mathrm{mod}m$이다.

페르마의 정리

페르마의 정리는 오일러의 정리의 특수한 경우이다.

• $p$가 소수이고 $a\in Z_p^{\ast }$일 때 $a^{p-1}=1\mathrm{mod}p$이다.

특수한 경우이므로 증명은 더 쉽다. 여기서는 생략.

중국인의 나머지 정리

중국인이는 말이 붙은 이유는 이 정리가 실제로 중국의 수학책에 쓰여 있었기 때문이다.

$m_1,m_2,\cdots ,m_r$이 모두 서로소라고 하자. 이때 $m=m_1{m}_2\cdots m_k$로 정의한다.

이때 임의의 $c_i\in Z_{m_i}(0\le c_i<m_i)$에 대해 $x=c_i\mathrm{mod}{m}_i$를 만족하는 $x$가 존재한다. 또한 그러한 $x$를 계산할 수 있다.

증명

$M_i=\frac{m}{m_i},N_i=(M_i{)}^{-1}\mathrm{mod}m$(곱셈의 역원)이라 하면 $x=\sum _{i=1}^r{c}_i{M}_i{N}_i\mathrm{mod}m$이다. 즉 $x=c_1{M}_1{N}_1+c_2{M}_2{N}_2+\cdots +c_r{M}_r{N}_r$이다.

정말로 그러한가? $x\mathrm{mod}{m}_i$를 계산해 보자. $M_j(j\ne i)$에는 모두 $m_i$가 곱해져 있다. 따라서 $x\mathrm{mod}{m}_i=c_i{M}_i{N}_i\mathrm{mod}m$인데 $M_i{N}_i=1\mathrm{mod}m$이므로 $x\mathrm{mod}{m}_i=c_i\mathrm{mod}m$이다. 이 식으로부터 $x=c_i\mathrm{mod}m$을 얻을 수 있다.

응용

$x=c_i\mathrm{mod}{m}_i,y=d_i\mathrm{mod}{m}_i(i=1,2,\cdots ,r)$이라 하면 $x+y=c_i+d_i\mathrm{mod}{m}_i$이고, $x\times y=c_i\times d_i\mathrm{mod}m$이다.

중국인의 나머지 정리를 이용하여 큰 수의 곱셈을 빠르게 계산할 수 있다. 곱하고자 하는 $x$와 $y$를 각각 $c_i$와 $d_i$로 쪼갠 다음 $c_i\times d_i\mathrm{mod}{m}_i$를 구하고, 이것을 이용하여 역으로 $x\times y$를 계산할 수 있다.

정수론을 마무리한다. 다음 시간에는 실제로 사용되는 암호에 대해 알아보자.