정수론 1#

• 설명: 수학의 한 분야로, 정수와 관련된 다양한 성질을 다루는 학문

  • 암호학에서 사용되는 정수론에서는 모든 자연수나 정수 범위보다도, 특정 값으로 나누는 나머지 연산이 높은 비중을 차지함

  1. 유클리드 알고리즘(Euclidean algorithm) 혹은 유클리드 호제법

     • 소인수분해 과정 없이도 두 수의 최대공약수(Greatest Common Divisor, GCD)를 구할 수 있음

     • 다음과 같은 사실을 기반으로 함

       1. a > b인 양의 정수 a, b에 대하여 a를 b로 나눈 나머지를 r로 정의하면, a, b의 최대공약수와 b, r의 최대공약수는 동일하다.
       2. a > 0일때, a, 0의 최대공약수는 a로 정의된다.

  2. 확장 유클리드 알고리즘(Extended Euclidean algorithm)

     1. 최대공약수(GCD)를 구하는 동시에, ax + by = gcd(a, b)를 만족하는 x, y를 찾아내는 알고리즘

     2. 사용 방법

        1. g = gcd(a, b)로 정의할 경우, 다음의 조건을 만족하는 정수 x, y는 항상 존재함
        2. a * x + b * y = g -> 조건을 만족하는 정수해 x, y는 유클리드 알고리즘을 구하는 방식과 동일하게 재귀적으로 구할 수 있음

     3. 서로소

        • 설명: 특별히 양의 정수 a, b의 최대공약수의 값이 1인 경우, a, b는 서로소(Coprime, Relatively prime) 관계에 있다고 표현함

        • 확장 유클리드 알고리즘을 사용하면 서로소 관계에 있는 양의 정수 a, b에 대해, a * x + b * y = 1을 만족하는 정수쌍 x, y를 찾을 수 있음

          • modulus에서의 역원을 구할 때 사용됨

  3. 합동식과 법

     1. 합동(Congruence)

        • 두 정수 a, b를 각각 양의 정수 m으로 나눈 나머지가 동일할 경우, “a, b는 m에 대하여 합동”이라고 표현함

          • 합동 관계를 작성한 수식을 합동식(Congruence relation)이라고 부름(a ≡ b (mod m))
          • a ≡ b (mod m)꼴의 합동식에서 m을 법 혹은 Modulus라고 부름

        • 암호학에서 중요한 합동식 규칙

          1. 교환법칙이 성립한다. 즉 a ≡ b (mod m)이 성립하면 b ≡ a (mod m)이 성립한다.
          2. a ≡ b (mod m), c ≡ d (mod m)이 성립하면 a ± c ≡ b ± d (mod m)이 성립한다.
          3. a ≡ b (mod m), c ≡ d (mod m)이 성립하면 a * c ≡ b * d (mod m)이 성립한다.
          4. a ≡ b (mod m)이 성립하면, 정수 k에 대하여 a^k ≡ b^k (mod m)이 성립한다.

     2. Modulus에서의 항등원과 역원

        1. 덧셈의 항등원과 역원

           1. 항등원의 경우

              • Modulus m 위에서 덧셈에 대한 항등원은 일반적인 덧셈에 대한 항등원과 동일한 0임. 물론, m, 2 * m, …등과 같이 표현 가능하지만, 모두 m으로 나눈 나머지는 0으로 동일하므로 생략함

           2. 역원의 경우

              • a에 대한 역원은 -a, 를 포함해 m - a, 2 * m - a, …와 같은 값들이 될 수 있음. 이 값들은 Modulus m 위에서 모두 동일함

        2. 곱셈의 항등원과 역원

           1. 항등원의 경우

              • Modulus m 위에서 곱셈에 대한 항등원은 일반적인 곱셈에 대한 항등원과 동일한 1임(a * 1 ≡ a (mod m))

           2. 역원의 경우

              • 상황에 따라 존재하거나 존재하지 않을 수 있음
              • a의 역원 a^-1이 존재한다고 가정하면, 다음의 식이 성립해야 함 -> a * a^-1 ≡ 1 (mod m)
              1. 역원이 존재하는 경우

                 • a, m의 최대공약수를 g라고 정의할 때, 좌변 a * a^-1은 a의 배수이므로 g의 배수임이 보장됨. 우변은 좌변에서 m을 정수 회 더하거나 뺀 값과 동일하고 m도 g의 배수이기 때문에 우변인 1도 g의 배수임이 보장됨

                 • 최대공약수 g가 1, 즉 a, m이 서로소 관계에 있는 경우에 역원이 항상 존재함

                   • 서로소인가? = 역원인가?

                 • a, m이 서로소일 경우, 확장 유클리드 알고리즘을 사용하여 a * x + m * y = 1을 만족하는 정수쌍 x, y를 찾을 수 있음

                   • 이 때 a * x = 1 - m * y이고, 1 - m * y ≡ 1이기 때문에 ax ≡ 1 (mod m)에 대한 역원의 조건을 만족함

  4. 중국인의 나머지 정리(Chinese Remainder Theorem, CRT)

     • 설명: 서로소인 두 modulus p,q 위에서 각각 x의 값이 유일하게 정해지는 경우, x는 modulus p * q 위에서도 항상 유일한 해가 존재한다.

     1. 해의 존재성

        • 증명할 것: x ≡ a (mod p), x ≡ b (mod q)일 때, x ≡ c (mod p * q)의 c 값을 구하는 방법
          1. q * β ≡ 1 (mod p)
          2. p * α ≡ 1 (mod q)
          3. 이 때, c = a * q * β + b * p * α로 정의하면 c ≡ a (mod p), c ≡ b (mod q)이 성립함을 알 수 있음
          4. c ≡ a * q * β + b * p * α ≡ a * q * β ≡ a * (q * β) ≡ a * 1 ≡ a (mod p)
          5. c ≡ a * q * β + b * p * α ≡ b * p * α ≡ b * (p * α) ≡ b * 1 ≡ b (mod q)
             • x ≡ c (mod p * q)일 때, x ≡ a (mod p), x ≡ b (mod q)를 만족하는 c가 항상 존재함

     2. 해의 유일성

        • 증명할 것: 해의 존재성에서 구한 c 이외의 다른 해는 존재하지 않고, c만이 유일한 해인 이유
          1. c₀이라는 값이 존재하여 c와 c₀는 p * q로 나눈 나머지가 서로 다르고, c₀ ≡ a(mod p), c₀ ≡ b (mod q)을 만족한다고 가정
          2. c₀ ≡ a ≡ c (mod p)이고, c₀ ≡ b ≡ c (mod q)이므로, c₀ - c는 p, q의 배수임
          3. p, q가 서로소이기 때문에, c₀ - c는 p * q의 배수이어야 하고, 이는 c와 c₀는 p * q로 나눈 나머지가 서로 다르다는 가정에 모순이 있음
             • 따라서 구한 c = a * q * β + b * p * α가 p * q의 modulus 위에서 유일한 해인 것이 증명됨

  5. Exponentiation by squaring

     • 용도: 큰 지수에 대한 거듭제곱을 연산할 때 사용되는 방법

     • e >= n에 대하여 n^e을 구하는 알고리즘

       1. e = 0인 경우: 곱셈의 항등원 반환
       2. e이 0보다 큰 짝수인 경우: n^e/2의 값을 구하여 (n^e/2)² 반환
       3. e이 0보다 큰 홀수인 경우: n^(e-1)/2의 값을 구하여 n * (n^e-1/2)² 반환
          • 일반 정수 범위에서 큰 거듭제곱을 연산할 일은 없지만, modulus 위에서의 연산인 경우 메모리 관련 문제가 없고, 큰 지수에 대한 거듭제곱을 계산할 일이 굉장히 많기 때문에 modulus 위에서의 거듭제곱 연산은 Exponentiation by squaring을 사용하기 적합함

1
def gcd(a, b): # 유클리드 알고리즘
2
    if b == 0:
3
        return a
4
    return gcd(b, a % b)
5

6

7
def xgcd(a, b): # 확장 유클리드 알고리즘
8
    if b == 0:
9
        # a = g = a * 1 + b * 0
10
        return a, 1, 0
11

12
    g, x1, y1 = xgcd(b, a % b)
13
    # g = x1 * b + y1 * (a % b)
14
    x = y1
15
    y = (g - a * x) // b
16
    assert a * x + b * y == g
17

18
    return g, x, y
19

20

21
def inverse(a, m): # 역원
22
    g, x, y = xgcd(a, m)
23

24
    if g != 1:
25
        # Inverse doesn't exist.
26
        return None
27
    return x
28

29

30
def crt(rem, mod): # 중국인의 나머지 정리에서 해의 존재성을 증명
31
    a, b = rem
32
    p, q = mod
33
    g, alpha, beta = xgcd(p, q)
34
    assert g == 1
35

36
    c = a * q * beta + b * p * alpha
37
    final_mod = p * q
38
    c %= final_mod
39

40
    assert c % p == a
41
    assert c % q == b
42

43
    return c, final_mod
44

45

46
def crt_multi(rem, mod): # 중국인의 나머지 정리에서 해의 유일성을 증명
47
    c = 0
48
    final_mod = 1
49
    for a, p in zip(rem, mod):
50
        c, final_mod = crt([c, a], [final_mod, p])
51

52
    for a, p in zip(rem, mod):
53
        assert c % p == a
54

55
    return c, final_mod
56

57

58
def mypow(n, e, m): # Exponentiation by squaring
59
    if e < 0:
60
        if gcd(n, m) == 1:
61
            return mypow(inverse(n, m), -e, m)
62
        else:
63
            # Inverse doesn't exist.
64
            return None
65

66
    elif e == 0:
67
        return 1
68

69
    elif e % 2 == 0:
70
        return mypow(n, e // 2, m)**2 % m
71

72
    else:
73
        return n * mypow(n, (e - 1) // 2, m)**2 % m