[보안] 기초 정수론 1

Contents

• 기본 수 체계
  • 항등원과 역원
  • 나눗셈과 가분성

• 약수와 최대 공약수
  • 유클리드 알고리즘
  • 확장 유클리드 알고리즘

• 최대 공약수의 활용

 

기본 수 체계

수 체계

 

항등원과 역원

항등원(Identity element)

• 임의의 원소 x에 특정 연산 ⊙를 수행하였을 때, x가 나오게 하는 원소 y
  • 1. 덧셈, 뺄셈 연산에 대한 항등원 → 0 ( ∵ x + y = x, x - y = x )
  • 2. 곱셈, 나눗셈 연산에 대한 항등원 → 1 ( ∵ x * y = x, x/y = x )

역원(Inverse element)

• 임의의 원소 x에 특정 연산 ⊙를 수행하였을 때, 해당 연산의 항등원이 나오게 하는 원소 y
  • 1. 덧셈 연산에 대한 역원 → -x ( ∵ x + y = 0, x - y = 0 )
  • 2. 곱셈 연산에 대한 역원 → 1/x ( ∵ x * y = 1, x/y = 1 )

정수 집합(Set Of Integers)

• 음의 무한대에서 양의 무한대까지의 모든 정수로 구성된 집합
• Z = { - ∞, ... , -2, -1, 0, 1, 2, ... , ∞ }
• a, b ∈ Z : 임의의 두 정수 a와 b를 의미.

이항 연산(Binary Operation)

• 두 입력 값으로부터 하나의 결과 값을 산출하는 연산
• 덧셈, 뺄셈, 곱셈
  
  • 나눗셈은 연산 결과로 몫과 나머지를 산출하므로, 이항 연산에 속하지 않는다.

 

 

 

나눗셈(Division)

a ∈ Z 를 n ∈ Z (n != 0)으로 나누면?

• 몫 : q ∈ Z
• 나머지 : r ∈ Z

a = qn + r

※제한 사항
1. n > 0
2. r ≥ 0

• a가 음수일 경우 q와 r은 음수이다. 이 때, r이 음이 아닌 정수라는 제약사항은 어떻게 적용해야 하는가?
  → q에서 1을 빼고, r에 n을 더하여 음이 아닌 정수로 만든다.
• 나눗셈은 상기의 등식으로 성립된다.
• 따라서, 나눗셈은 이항 연산이 아닌 관계식이다.

나눗셈 정리

• 임의의 두 정수 a, b ∈ Z ( b > 0 )가 존재한다면, a = qb + r을 만족하는 두 정수 q, r ∈ Z이 항상 유일하게 존재한다.

가분성(Divisibility)

• a를 n으로 나눌 때, 나머지가 0이라면(즉, a = qn + r 에서 r = 0)
  • n은 a의 약수(divisor)이다.
  • a는 n으로 나눌 수 있다.

• a를 n으로 나눌 때, 나머지가 0이 아니라면(즉, a = qn + r 에서 r > 0)
  • n은 a의 약수가 아니다.
  • a는 n으로 나눌 수 없다.

 

가분성의 주요 성질(properties)

• 가분성의 주요 성질
  • Property 1. 만약 a | 1 이면 a = +- 1
  • Property 2. 만약 a | b 이고 b | a 이면 a = +- b
  • Property 3. 만약 a | b 이고 b | c 이면 a | c
  • Property 4. 만약 a | b 이고 a | c 이면 a | (mb + nc)

Property 1

• Property 1. 만약 a | 1 이면 a = +- 1
• [증명]
  • a | 1 ☞ 1 = xa 이다. 이 때 x는 정수이다.
  • 이것이 의미하는 바는 " x = 1 이고, a = 1" 이거나 " x = -1 이고  a = -1 "이다.
  • 따라서 a = +- 1 이다.

Property 2

• Property 2. 만약 a | b 이고 b | a 이면 a = +- b
• [증명]
  • a | b ☞ b = xa 이다. 이 때 x는 정수이다.
  • b | a ☞ a = yb 이다. 이 때 y는 정수이다.
  • 따라서, a = y(xa) = yx(a) ☞ yx = 1 이다.
  • 이것이 의미하는 바는 "x = 1 이고, y = 1" 이거나 "x = -1 이고 y = -1" 이다.
  • 따라서 a = yb  ☞ a = +-b

Property 3

• Property 3. 만약 a | b 이고 b | c 이면 a | c
• [증명]
  • a | b ☞ b = xa 이다. 이 때 x는 정수이다.
  • b | c ☞ c = yb 이다. 이 떄 y는 정수이다.
  • 따라서, c = y(xa) = (yx)a 이다.
  • 그러므로, a | c 이다.

Property 4

• Property 4. 만약 a | b 이고 a | c 이면 a | (mb + nc) where m,n ∈ Z
• [증명]
  • a | b ☞ b = xa 이다. 이 때 x는 정수이다.
  • a | c ☞ c = ya 이다. 이 때 y는 정수이다.
  • 따라서, mb + nc = m(xa) + n(ya) = (mx + ny)a 이다.
  • 그러므로, a | (mb + nc) 이다.

가분성의 주요 성질(properties) 예제

• 만약 3 | 15 이고 15 | 45 이면 3 | 45는 참(true)인가?
  → Yes(Property 3)
• 만약 3 | 15 이고 3 | 9 이면 3 | 66은 참(true)인가?
  → Yes(Property 4)

 

약수와 최대공약수

공약수
: 두 양의 정수가 갖는 공통의 약수

최대 공약수(Greatest Common Divisor: GCD)
: 두 양의 정수의 공약수 중에서 가장 큰 정수
: 두 양의 정수의 최대 공약수 = 두 정수를 나누는 가장 큰 정수

유클리드 알고리즘(Euclidean Algorithm)

• 두 양의 정수의 최대 공약수를 찾는 알고리즘
• 약 2000년 전에 수학자 유클리드가 고안
• 기본 원리
  • gcd(a, 0) = a
  • gcd(a, b) = gcd(b, r) where r = a를 나눈 나머지
• [정리] 만약 a = bq + r이라면, gcd(a, b) = gcd(b, r)이다.
• 증명
  • r을 a와 b의 나머지, g를 a와 b의 최대공약수라고 하자(즉, gcd(a,b) = g).
  • a를 b로 나눈다면, 이는 a = b·q + r을 만족하므로, a = c1·g, b = c2·g 로 나타낼 수 있다.
  • 그렇다면 a = b·q + r 은 c1·g = c2·g·q + r로 표현할 수 있다. 따라서,
    c1·g = c2·g·q + r ☞ r = c1·g - c2·g·q = (c1 - c2·q)·g
  • 즉, 나머지 r도 동일한 최대공약수 g를 갖는다. 따라서,
    a와 b의 최대공약수 g를 구하는 것은 b와 r의 최대공약수를 구하는 것과 동일하다.
• (예) 36과 10의 최대공약수를 유클리드 알고리즘으로 계산하라.

• 표로 작성해서 구하는 법

a	b	r(나머지)	q(몫)
36	10

36	10	6	3
10	6

10	6	4	1
6	4

6	4	2	1
4	2

4

2

0

2

2

0

답은 2.

확장 유클리드 알고리즘(Extended Euclid Algorithm)

• 두 개의 정수 a와 b가 주어졌을 때, gcd(a,b)와 함께 다음을 만족하는 다른 두 정수 s와 t를 동시에 계산한다.
  
  sa + tb = gcd(a,b)
  
  
• 핵심 공식 :        r = r1 - q·r2 ,        s = s1 - q·s2 ,        t = t1 - q·t2
• 초기화 식 :        r1 ← a, r2 ← b ,         t1 ← 0, t2 ← 1 ,       s1 ← 1, s2 ← 0

 

• (예) a = 161, b = 28일 때, gcd(a,b)와 s,t를 구하시오.
  • 초기화 식 : r1 ← 161, r2 ← 28, t1 ← 0, t2 ← 1
  • 핵심 공식 : r = r1 - q·r2,    s = s1 - q·s2,    t = t1 - q·t2

 

최대 공약수의 활용

선형 디오판투스 방정식(Linear Diophantine equations)

• 두 변수 a와 b를 가진 ax + by = c 형태의 선형방적식
  • 상기 방정식에서, d = gcd(a, b)라 하자.
  • 만약 d † c 이면, 상기 방정식의 해는 존재하지 않음.
  • 만약 d | c 이면, 무수히 많은 해가 존재한다.
    • 이 중에서, 특정 하나의 해 → 특수 해 (particular solution)
    • 나머지 해 → 일반 해 (general solution)
• 특수 해 구하는 방법
  • d | c 이면 ax + by = c의 특수 해 x$_0$와 y$_0$를 아래와 같이 구할 수 있다.
  • ① d로 방정식의 양변을 나누어, a$_1$x + b$_1$y = 1을 만족하는 s와 t를 계산한다.
  • ② 확장 유클리드 알고리즘을 이용하여 식 a$_1$s + b$_1$t = 1을 만족하는 s와 t를 계산한다.
  • ③ 특수 해 x$_0$와 y$_0$는 다음과 같이 계산된다.
• 일반 해 구하는 방법
  • d | c 이면, ax + by = c의 특수 해 x$_0$ 와 y$_0$ 로부터 일반 해 x와 y를 아래와 같이 구할 수 있다.

x = x$_0$ + k$(\frac{a}{b})$, y = y$_0$ - k$(\frac{a}{b})$

where k ∈ $Z$

• (예) 21x + 14y = 35의 특수 해와 일반 해를 구하시오.
  • gcd(21, 14) = 7 = d → 7 | 35 이므로, 위 방정식은 무한히 많은 해를 갖는다.
  • 양 변을 d = 7로 나누어 상기의 방정식을 3x + 2y = 5로 변환한다.
  • 확장 유클리드 알고리즘을 이용하여 3s + 2t = 1을 만족하는 s, t를 계산한다. → s = 1, t = -1
  • 특성 해와 일반 해를 아래와 같이 계산하다.
    • 특수 해 : x$_0$ = 5, y$_0$ = -5
    • 일반 해 : x = 2k + 5, y = -3k - 5