×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 797,258명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)


목차


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




소스 코드 : 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#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,};
    t = { 0,};
    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 >>
Crocus


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

위에서 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값을 더해주어 양수로 바꾸면 양수 역원을 구할 수 있다.





  1. thank 2019.03.05 14:28

    모듈러 인버스에서
    2*n mod 11 사이에 3*n mod 11이 하나 껴있는데
    오타인가요?