이동식 저장소

10주차 2차시 본문

CS/암호학

10주차 2차시

해스끼 2020. 11. 11. 09:55

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

 

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

Reduced Residue System Zm={a|gcd(a,m)=1, 0a<m}

Zm에서 곱셈이 잘 정의된다는 것을 증명한다.

aZm,  x  ax=1modm

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

(ab)c=a(bc)modm (곱셈의 결합법칙) 증명

a=q1m+a1, b=q2m+b1, c=q3m+c1이라 하면 (ab)c=((q1m+a1)(q2m+b1))(q3m+c1)=(q1q2m2+aq2m+bq1m+a1b1)(q3m+c1)이고, a(bc)=(q1m+a1)((q2m+b1)(q3m+c1))=(q1m+a1)(q2q3m2+bq3+cq2m+bc)이다. 두 식을 전개해서 정리하면 양변이 같음을 알 수 있다. 양변이 같으므로 양변을 m으로 나눈 나머지도 같다. 따라서 (ab)c=a(bc)modm이다.

 

사실 Zm에서는 덧셈과 뺄셈이 잘 정의되지 않는다.

Real Number System

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

 

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

 

예를 들어 a,bRa+bR은 공리이다. aRaR도 공리이다. 이런 공리가 모두 성립한다고 생각하다 보면 더 복잡한 성질을 이끌어낼 수 있다. 

 

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

다시 돌아와서

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

 

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

오일러의 정리

aZm에 대해 a1,a2,a3, modm는 모두 Zm의 원소이다. Zm는 유한하므로 a의 제곱을 계속 계산하다 보면 비둘기집의 원리에 의해 언젠가는 ai=ajmodm를 만족한다. i<j라 놓으면 ai=ai×ajimodm이므로 1=ajimodm이다. Zm이 나눗셈에 대해 닫혀있기 때문에 양변을 ai로 나눠도 등식이 성립한다.

 

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

 

  • aZmaφ(m)=1modm (φ(m)=|Zm|)

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

증명

Zm={a1,a2,,ak}라 하면 φ(m)=k이다. a=ai (1ik)라 하면 aZm={aa1,aa2,,aak}Zm이다. Zm이 곱셈에 대해 닫혀있으므로 aajZm이다. 그런데 ij이면 aaiaajmodm이므로 aZm의 모든 원소는 서로 다르고, 따라서 aZm=Zm이다.

 

따라서 aa1×aa2×aak=a1×a2××akmodm이다. 좌변은 aZm의 원소를 모두 곱한 것이고, 우변은 Zm의 원소를 모두 곱한 것이다. 두 집합이 같으므로 두 집합의 모든 원소를 곱해도 같다.

 

좌변을 정리하면 ak×a1×a2××ak=a1×a2×akmodm이고, 따라서 ak=1modm이다.

페르마의 정리

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

 

  • p가 소수이고 aZp일 때 ap1=1modp이다.

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

중국인의 나머지 정리

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

 

m1,m2,,mr이 모두 서로소라고 하자. 이때 m=m1m2mk로 정의한다.

이때 임의의 ciZmi (0ci<mi)에 대해 x=cimodmi를 만족하는 x가 존재한다. 또한 그러한 x를 계산할 수 있다.

증명

Mi=mmi, Ni=(Mi)1modm(곱셈의 역원)이라 하면 x=ri=1ciMiNimodm이다. 즉 x=c1M1N1+c2M2N2++crMrNr이다.

 

정말로 그러한가? xmodmi를 계산해 보자. Mj (ji)에는 모두 mi가 곱해져 있다. 따라서 xmodmi=ciMiNimodm인데 MiNi=1modm이므로 xmodmi=cimodm이다. 이 식으로부터 x=cimodm을 얻을 수 있다.

응용

x=cimodmi, y=dimodmi (i=1,2,,r)이라 하면 x+y=ci+dimodmi이고, x×y=ci×dimodm이다.

 

중국인의 나머지 정리를 이용하여 큰 수의 곱셈을 빠르게 계산할 수 있다. 곱하고자 하는 xy를 각각 cidi로 쪼갠 다음 ci×dimodmi를 구하고, 이것을 이용하여 역으로 x×y를 계산할 수 있다.

 

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

 

'CS > 암호학' 카테고리의 다른 글

12주차 1차시  (0) 2020.11.19
11주차 2차시  (0) 2020.11.15
10주차 1차시  (0) 2020.11.04
9주차 1차시  (0) 2020.10.29
6주차 1차시  (0) 2020.10.08