05. 모듈러 산술(Modular Arithmetic), 중국인의 나머지 정리

모듈러 산술(Modular Arithmetic)

* 암호학에서 굉장히 많이 다뤄지는 부분이므로 잘 이해해야 한다.

모듈러 산술은 나머지 연산을 말한다. 실생활에서 시계의 경우가 대표적인데, 시계가 시간을 표시하는 것은 0에서 부터 11시까지만이다. 12시가 되면 다시 0이되고 13은 1, 14는 2가 되면서 11까지 반복된다. 즉, 시계는 12로 나눈 나머지만을 수로 가진다.(물론 시침과 분침을 가지는 아날로그형 시계인 경우만을 얘기한다. 13시를 그냥 13시로 표시하며 24시까지 표현하는 경우는, 24로 나눈 나머지를 수로 가진다)

 

이를 식으로 표현하면 다음과 같다.

   1시: 1 (mod 12)

   6시: 6 (mod 12)

   11시: 11 (mod 12)

   12시: 0 (mod 12)

   15시: 3 (mod 12)

 모듈러 산술에 대한 수학적인 정의는 다음과 같다.

a,b,n은 정수이고 n≠0 일 때, n | (a-b) 이면, a와 b는 모듈러 n에 대해 합동이라하고, a ≡ b (mod n) 이라 표현한다. 

시계의 예를 보면 15시 3(mod 12)이다. 이를 위 정의에 대입해서 생각해 보면, 15 ≡ 3 (mod 12) 이고, 이는 12 | (15-3) 이기 때문이다.

(그냥 15는 12로 나눴을 때 나머지가 3이니깐, 15 ≡ 3 (mod 12) 이라고 생각하는 것이 편하다. 그러나, 미지의 두 수 a, b가 있을 때 이 두수가 n에 대해서 합동인가를 따져야할 때는, 두 수의 차인 (a-b)를 하고, n이 (a-b)의 약수인가를 따지는 것이 편하기에, 위 정의를 잘 음미할 필요가 있다.)

a ≡ b (mod n)에서, n은 모듈러스(modulus)라고 부르고, a는 b와 합동관계(congruence relation)에 있다라고 한다.

모듈러 산술에 대해 여러 기본적인 성질들이 있는데, 대부분 직관적이기에 생략하고, 중요하면서도 좀 머리를 써서 생각해야하는 몇 가지에 대해 좀 상세히 알아보도록 하자

• 중국인의 나머지 정리
• Garner's Algorithm
• 페르마의 소정리
• 오일러 법칙

중국인의 나머지 정리(Chinese Remainder Theorem)

어떤 수 x에 대해 x ≡ 2 (mod 3) ≡ 3 (mod 5) ≡ 2 (mod 7) 이라고 한다. x는 무엇인가?

이런 문제를 풀려면 어떻게 해야할까?

놀랍게도 광개토대왕과 장수왕 시절인 5세기 중국 남북조시대의 수학서인 '손자산경'에 나온 문제라 한다.

"개수를 알지 못하는 어떤 것이 있다. 셋씩 센다면 두 개가 남고, 다섯씩 센다면 세 개가 남고, 일곱씩 센다면 두 개가 남는다. 총 몇개인가?"

今有物，不知其數。三三數之，賸二；五五數之，賸三；七七數之，賸二。問：物幾何？

답은 23이다. '손자산경'에 나온 풀이는 다음과 같다. (출처:wikipedia)

셋씩 세어 두 개가 남으면, 140을 적는다. 다섯씩 세어 세 개가 남으면 63을 적는다. 일곱씩 세어 두 개가 남으면 30을 적는다. 

이들을 더해 233이 되고, 210을 빼면 정답을 얻는다. 마찬가지로, 셋씩 세어 한 개가 남으면 70을 적는다. 다섯씩 세어 한 개가 남으면 21을 적는다. 일곱씩 세어 한 개가 남으면 15를 적는다. 합이 106보다 더 크므로, 105를 빼면 정답을 얻는다.

術曰：三三數之，賸二，置一百四十；五五數之，賸三，置六十三；七七數之，賸二 ，置三十。并之，得二百三十三，以二百一十減之，即得。凡三三數之，賸一，則置七十；五五數之，賸一，則置二十一；七七數之，賸一，則置十五。一百六以上，以一百五減之，即得。

무슨 말인지 바로 이해가 된다면 아래 설명 부분은 보지 않아도 된다..^^

왜 갑자기 "셋씩 세어 두 개가 남으면 140을 적고, 다섯씩 세어 세 개가 남으면 63을 적는다..." 등을 이해하려면, 아래 중국인의 나머지 정리를 이해하고, 그 방식대로 복잡하게 문제를 풀어나가야 한다. 

(중국인의 나머지 정리)

1이 아닌 양의 정수들 m1, … , mn이 둘 씩 서로소라고 가정하면, 임의의 0이 아닌 정수들 a1, … , ar 에 대해,

       x ≡ a1 (mod m1), … , x ≡ ar (mod mr)

은 해를 가지게 되고, 모듈러 m = m1·m2· ...· mr에 대해 유일하다.

이 때, 그 해 x의 값은 다음과 같다.

여기서 bj는 (m/mi)bj ≡ 1 (mod mj), j=1, ... , r 을 만족하는 수를 말한다.

손자산경에 나온 예는 x = 2(mod 3) = 3(mod 5) = 2(mod 7) 이었다. 

위 정리에 나온 표현으로 보면 a1=2, a2=3, a3=2이고, m1=3, m2=5, m3=7이이고 서로 소이다.(m1,m2,m3이 전부 소수이므로 당연 서로 소이다)

a1=2, a2=3, a3=2

m1=3, m2=5, m3=7 -->m = m1·m2·m3 = 3·5·7 = 105

b1, b2, b3 을 구해보면,

(m/m1)b1 ≡ 1(mod m1) ⇔ (105/3)b1 = 35·b1≡ 1(mod 3) ⇔ 2·b1≡ 1(mod 3) 따라서, b1 = 2

(m/m2)b2 ≡ 1(mod m2) ⇔ (105/5)b2 = 21·b2≡ 1(mod 5) ⇔ 1·b2≡ 1(mod 5) 따라서, b2 = 1

(m/m3)b3 ≡ 1(mod m3) ⇔ (105/7)b1 = 15·b3≡ 1(mod 7) ⇔ 1·b3≡ 1(mod 7) 따라서, b3 = 1

해 x는,

x = (m/m1)b1·a1 + (m/m2)b2·a2 + (m/m3)b3·a3 = 35·2·2 + 21·1·3 + 15·1·2 = 140 + 63 + 30 = 233 ≡ 23 (mod 105)

계산이 좀 복잡한데, 실제 손으로 풀어야한다면 아래와 같이 a와 m값을 차례로 적어 놓고, 순서대로 풀면 된다. (나름 규칙성이 있어 풀만하다)

두 개의 조건이 주어졌을 때는 어떻게 될까? 즉, x = 2(mod 3) = 3(mod 5)를 만족하는 x는?

풀면 다음과 같다.

a: 2, 3

m: 3,5 --> 15

2 x 5 x (5^-1 mod 3) = 10 x 2 = 20

3 x 3 x (3^-1 mod 5) = 9 x 2 = 18

                                      ----------

                                      38 mod 15 = 8

 

Garner's Algorithm

중국인의 나머지 정리에 나오는 문제를, 위에서 소개한 '손자산경'에 나오는 방법보다 좀 더 효율적으로 푼 것이 Garner's Algorithm이다. (Harvey. L. Garner, "The Residue Number System", 1959)

(Garner's Algorithm)

mi < Z (0 ≤ i ≤ n) 인  양수 모듈러 mi가 서로 소인 여러 수들의 곱으로 나타낼 수 있고(m = m1 x m2 x ... x mn), 각각 대응하는 해 ui가  ui ∈Z (0 ≤ i ≤ n) 일 때, u = ui (mod mi) 를 만족하는 유일한 u는 다음과 같이 나타낼 수 있다.  

   

여기서 vi = ui (mod mi)

Garner's Algorithm을 이용해서 u = 4(mod 5) = 1(mod 7) = 2(mod11)를 만족하는 u를 구해보자. 

공식에 의해 u는 다음과 같이 나타낼 수 있다.

u = v0 + v1·5 + v2·5·7

이제 각각 주어진 값(4 mod5, 1mod7, 2mod11)을 이용해서 v0,v1,v2를 차례로 구할 수 있다.

u = 4mod5 ==> v0 + v1·5 + v2·5·7 = 4mod5 ==> v0 = 4mod5 

∴ u = 4 + v1·5 + v2·5·7

u = 1mod7 ==> 4 + v1·5 + v2·5·7 = 1mod7 ==> 4 + v1·5 = 1mod7  ==>  v1·5 = -3 = 4mod7

==> v1 = 12 = 5mod7 (왜냐하면 5^-1mod7=3)

∴ u = 4 + 5·5 + v2·5·7

u = 2mod11 ==> 4 + 5·5 + v2·5·7 = 2mod11 ==> 29 + v2·5·7 = 2mod11  ==> 7 + v2·35 = 2mod11  

==> v2·2 = -5 = 6mod11  ==> v2 = 36 = 3 mod11 (왜냐하면 2^-1mod11=6)

∴ u = 4 + 5·5 + 3·5·7 = 4 + 25 + 105 = 134 (mod 5·7·11)

Garner's Algorithm이 중국인의 나머지 정리보다 효율적이라고 하는 이유는, 계산하는 식에서 모듈러스 m을 사용한 계산이 없다는데 있다. 즉, 중국인의 나머지 정리에서는 제일 마지막에 m을 이용한 모듈라 연산을 해야하는데 반해, Garner's Algorithm에서는 곱해서 m이 되는 값들인  mi만을 이용해서 계산이 가능하고, mi가 m에 비해서 작은 값들이므로, 작은 수로의 모듈라연산에서 오는 이득을 볼 수 있다. (RSA 알고리즘의 경우, 두 소수 p,q의 곱인 n에 대한 모듈라연산을 수행하게 되는데, Garner's Algorithm을 이용하면 n이 아닌 p와 q에 의한 모듈라연산을 사용할 수 있어, 연산속도를 개선할 수 있다.)

    

페르마의 소정리 (Fermat's Little Theorem)

페르마의 소정리는, "소수 p를 법으로하는 모듈러연산에서 양의정수 a와 a^p는 서로 합동"이라는 것이다.

(페르마의 소정리)

a가 양의정수이고, p가 소수라면,

a^p ≡ a (mod p)

예를 들어, 소수 5을 법으로 하는 수 체계에서, 2⁵≡ 2 이고, 3⁵≡ 3, 4⁵≡ 4 가 된다는 것이다.

2⁵의 경우를 계산해 보면, 2⁵= 32 = 2 mod 5

3⁵의 경우를 계산해 보면, 3⁵= 243 = 3 mod 5

4⁵의 경우를 계산해 보면, 4⁵= 1024 = 4 mod 5

페스마의 소정리가 암호학에서 중요하게 쓰이는 이유는, 어떤 수가 소수인지 아닌 지를 판가름하는 '소수판정 알고리즘'과 오일러정리(바로 뒤에 나옴)의 증명으로 사용될 수 있기 때문이다.

소수판정알고리즘으로 많이 사용되는 Rabin-Miller방식은, 페르마의 소정리를 기본 원리로 하고 있다.

(Rabin-Miller판정방법에 대한 상세사항은 여기 참조) 

(Rabin-Miller에 의한 소수판정방법) 

단계 1. n-1를 2로 나누어질 때까지 나누어, n–1 = 2^sd 를 만족하는 s와 d을 구함

단계 2. a < n인 a를 임의로 선택함
단계 3. z = a^s mod n를 계산함
단계 4. z = 1이면 n은 테스트를 통과함. 즉, 소수
단계 5. for i = 0 to s-1 do
                if(z = n–1) -> 테스트 통과
                else z := z² mod n

a^p ≡ a (mod p)에서 양변을 a로 나누면 a^p-1 ≡ 1 (mod p) 가 되고, 이는 오일러정리의 한 형태이고, 이를 이용해서 오일러정리를 증명할 수 있다.

오일러 정리(Euler's Theorem)

a와 n이 서로소인 양의 정수들이라 하면, a^φ(n) ≡ 1 (mod n)이다.

여기서 φ(n)은 오일러파이함수로 1부터 n까지의 양의정수 증에 n과 서로 소인것의 개수를 나타낸다.

페르마의 소정리를 이용하면 쉽게 정리할 수 있다.

(오일러정리의 증명)

n을 소인수 분해한 것을 n = p1^a1 …pk^ak이라 하면,  a^pi-1 ≡ 1 (mod pi) 이므로,

a^pi(pi-1) ≡ 1 (mod pi² ),  a^pi2(pi-1) ≡ 1 (mod pi² ),

즉, 모든 i = 1, …, k에 대해 아래 식이 성립한다.

이 것을 각가의 소인수에 적용하면 증명이 완성된다.

오일러 파이함수 Φ(n)은  다음과 같이 구해진다.

여기서 pi는 n의 소인수 .

만약 n의 소수이면 Φ(n) = n-1이다. (왜냐면 공식에 의해, Φ(n) = n x (1-1/n) = n - 1)

여기서 pi는 n의 소인수 .

만약 n의 소수이면 Φ(n) = n-1이다. (왜냐면 공식에 의해, Φ(n) = n x (1-1/n) = n - 1)

오일러의 정리를 이용하면, 큰 지수에 대한 모듈라연산을 작은 지수로 변환해서 쉽게 계산할 수 있다.

예를 들어 2009¹⁰⁰² (mod 100) 을 계산해보자.

Φ(100) = 100 x (1-1/2) x (1-1/5) = 40 (왜냐하면 100 = 2² x 5²)

따라서, 오일러 정리에 따라, 100과 서로소인 2009에 대해서 2009⁴⁰ ≡ 1 (mod100)

1002를 40을 이용해서 표현하면, 1002 = 40 x 25 + 2 따라서, 

2009¹⁰⁰² =  2009^40x25+2 = 2009^40x25·2009²(mod100) = 2009²(mod100) (∵2009⁴⁰ ≡ 1 mod100)

2009²(mod100) = 9² = 81 mod 100

-끝-