모듈러 연산(Modular Arithmetic)

---

목차

1. 모듈러 연산

2. 모듈러 합동

3. 모듈러 연산의 속성

4. 모듈러 인버스

5. 확장 유클리드 알고리즘을 이용한 곱셈 역수(역원) 구하기

---

1. 모듈러 연산

몇 가지 중요한 암호 시스템은 계산 결과가 항상 0 - (m-1) 범위에있는 경우 모듈러 연산을 사용한다.

이때 m은 %를 하고자 하는 modular 값이다.

우리가 익히 알고있는 모듈러 연산을 해보자.

17 mod 5 = 2

7 mod 11 = 7

20 mod 3 = 2

11 mod 11 = 0

음수의 경우에도 모듈러 연산이 가능하다.

-3 mod 11 = 8

-1 mod 11 = 10

25 mod 5 = 0

-11 mod 11 = 0

음수를 mod 할 경우에는 양수라 생각하고 mod를 한 후 + m을 해주면 된다.

예를 들어 -20 mod 11이면 20 mod 11 = 9 에서 -9 + 11 = 2와 같다.

2. 모듈러 합동

 

(a mod n) = (b mod n)  -> a ≡ b(mod n)

어떤 값 A와 B가 n으로 나누었을 때 나머지가 같다면 A와 B는 모듈 C에 대한 합동 관계라고 한다.

그러한 A와 B는 A - B를 하였을 때 k*n과 같다.

즉, A - B = kn으로 나타낼 수 있다.

예를들어보자.

4와 9는 mod 5로 인해 나머지가 4로 동일하다.

4 - 9 = -5 = -1*5로 나타낼 수 있다.

이로인해 우리는 다음과 같이 합동의 특성을 나타낼 수 있다.

3. 모듈러 연산의 속성

1. (a + b) mod n = ((a mod n) + (b mod n)) mod n

2. (a - b) mod n = ((a mod n) - (b mod n)) mod n

** 알아두기 **

((a mod n) - (b mod n)) mod n에서 a = 3, b = 5, n = 6이면 -2 mod 6 = -2가 나온다.

이때 '-' 연산을 이용할 때 mod를 쓰는 일이 있다면 ((a mod n) - (b mod n)) mod n + n을통해 양수로 만들어 줄 수 있다.

3. (a * b) mod n = ((a mod n) * (b mod n)) mod n

1번 속성에 대한 증명은 다음과 같다.

이를 통해 거듭제곱을 가지는 값에 모듈러를 한다면 곱셈의 원리를 이용하여 해결 할 수 있다.

빠른 모듈러 거듭제곱법은 다음 사이트를 확인하자. 

https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-exponentiation

몇가지 예제를 통해 맞는지 확인해보자.

11 mod 8 = 3; 15 mod 8 = 7

(11 + 15) mod 8 = 26 mod 8 = 2

((11 mod 8 ) + (15 mod 8)) mod 8 = 10 mod 8 = 2

(11 - 15) mod 8 = -4 mod 8 = 4

((11 mod 8 ) - (15 mod 8)) mod 8 = -4 mod 8 = 4

(11 x 15) mod 8 = 165 mod 8 = 5

((11 mod 8 ) x (15 mod 8))  mod 8= 21 mod 8 = 5

4. 모듈러 인버스

모듈러 역수(역원)에 대해 알아보고자 한다.

우선 13/14 mod 11은 몇일까?

우선 13 * 14^-1 mod 11로 생각해보자.

그렇다면 모듈러 특성에 의해 ((13 mod 11) * (14 mod 11)^-1) mod 11이 되고 2 * 3^-1 mod 11이 된다.

이때 3^-1을 N으로 두자.

그러면 2 * N  mod 11이 되고 N을 구하기 위해서는 3 * x mod 11 = 1이 되는 x를 찾으면 된다.

x는 결국 4, 15, 26, 37 ...이 됨을 알 수 있다.

따라서 13/14 mod 11 = 2 * N mod 11 = 2 * 4 mod 11 = 8이 된다.

이제 이를 좀더 자세하게 보자.

(5 / 3) mod 11은 뭘까?

우리는 곱의 형태인 (5 * 3^-1) mod 11로 나타낼 수 있다.

우리는 어떤 숫자에 역수를 곱하면 그 결과값은 1이 나와야한다.

예를들면 2 의 역수인 2^-1 즉, 1/2 둘을 곱하면 2*(1/2) = 1이다.

3 * x mod 11은 1이 나와야하므로 x = 4라는 역수를 구할 수 있다.

물론 x = 1/3도 되지만 분수 값이 아닌 정수 값으로 구하고 mod 11이라는 모듈러가 있기에 4도 가능해진다는 것이다.

따라서 우리는 5 / 3 mod 11이 5 * 3^-1 mod 11과 같으며 5 * 4 mod 11과 같고 결국 9라는 답을 도출 할 수 있다.

5. 확장 유클리드 알고리즘을 이용한 곱셈 역수(역원) 구하기

확장 유클리드 알고리즘으로 나머지 연산의 곱셈 역수를 구해보려한다.

확장 유클리드 알고리즘에 대한 자세한 내용은 아래 링크에서 확인 할 수 있다.

http://www.crocus.co.kr/1232

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
struct INFO {
    int gcd;
    int s;
    int t;
};
vector<int> s, t, r, q;
INFO xGCD(int a, int b) {
    s = { 1,0 };
    t = { 0,1 };
    r = { a,b };
 
    while (1)
    {
        int r2 = r[r.size() - 2];
        int r1 = r[r.size() - 1];
        q.push_back(r2 / r1);
        r.push_back(r2 % r1);
        
        if (r[r.size() - 1] == 0)
            break;
 
        int s2 = s[s.size() - 2];
        int s1 = s[s.size() - 1];
 
        int t2 = t[t.size() - 2];
        int t1 = t[t.size() - 1];
        
        int q1 = q[q.size() - 1];
        s.push_back(s2 - s1 * q1);
        t.push_back(t2 - t1 * q1);
    }
 
    // return gcd, s, t
    INFO ret = { r[r.size() - 2], s[s.size() - 1], t[t.size() - 1] };
 
    s.clear(), t.clear(), r.clear(), q.clear();
 
    return ret;
}
int main()
{
 
    int a, b;
    scanf("%d %d", &a, &b);
    if (b > a)
        swap(a, b);
    INFO ret = xGCD(a, b);
 
    printf("gcd :: %d s :: %d t :: %d", ret.gcd, ret.s, ret.t);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

위의 코드에 자신이 구하고자하는 곱셈의 역수를 구하려는 곱셈 값과 모듈러 값을 넣어보자.

위에서 14의 역원과 3의 역원을 이용해봤으니 14 11과 3 11을 넣어보자.

14 11 gcd :: 1 s :: 4 t :: -5

3 11

gcd :: 1 s :: -1 t :: 4

이때 의미하는 것은 14 11을 넣을때는 swap가 없으니 s값이 결국 역원이 되는 것이고

3 11에서는 swap을 하게 되니 t값이 결국 역원이 된다.

만약 역원(역수)이 음수라면 + mod값을 더해주어 양수로 바꾸면 양수 역원을 구할 수 있다.