chapter 2 암호 수학 - 1절 정수 연산

1. 정수 집합

 정수 집합(set of integers)Z는 음의 무한대에서 양의 무한대까지의 모든 정수로 구성된 집합이다.

 

2. 이항 연산

 이항 연산(binary operations)이란 두 개의 입력 값으로부터 하나의 결과 값을 산출하는 연산이다. 가령, 더하기, 뺴기, 곱하기가 이항 연산에 포함된다. 나눗셈은 결과값이 두개이므로 이항 연산이 아니다.

 

3. 정수의 나눗셈

 정수 연산에서 a를 n으로 나누면 q와 r을 얻는다. a를 피제수, q를 몫, n을 제수, r을 나머지라고 부른다. 나눗셈은 연산이 아니고, 나눗셈 관계식(division relation)이다. 암호에서 나눗셈 관계식을 이용할 때는 제수가 양의 정수(n>0)여야 하며, 나머지는 음이 아닌 정수(r>=0)여야 한다는 제약이 따른다. 또한 나눗셈 관계식을 관계 그래프에 나타낼 수도 있다.

 

4. 가분성

 가분성(divisibility)이란 나눌 수 있는 성질을 말한다. 나눗셈 관계식에서 a != 0와 r = 0조건을 추가하면 a=q*n가 된다. 여기서 'n은 a를 나눈다'라고 하며 n|a로 표현한다.

 1. 성질
 성질 1 : a|1 → a = ±1
 성질 2 : a|b ^ b|a → a = ±b
 성질 3 : a|b ^ b|c → a|c
 성질 4 : a|b ^ a|c → a|(m*b + n*c)  (단, m∈Z, n∈Z)

 2. 모든 약수
 모든 양의 정수는 하나 이상의 약수(divisor)를 갖는다. 모든 양의 정수는 항상 1과 자기 자신을 약수로 가진다.
 
3. 최대 공약수
 최대 공약수(greatest common divisor, gcd)는 두 양의 정수 사이에 단 하나만 존재한다.
 
4. 유클리드 알고리즘
 유클리드 알고리즘(euclidean algorithm)은 두 양의 정수의 최대 공약수를 찾아내는 알고리즘이다. gcd(a, 0) = a라는 사실과 gcd(a, b) = gcd(b, r)일 때 r은 a를 b로 나눈 나머지라는 사실을 이용한다.

 5. 확장 유클리드 알고리즘
 확장 유클리드 알고리즘(extended euclidean algorithm)은 s*a + t*b = gcd(a,b)에서 gcd(a,b), s, t를 동시에 계산한다. 유클리드 알고리즘에 두 쌍의 계산과 교환이 추가된다.

 

5. 선형 디오판투스 방정식

 두 변수를 가진 선형 디오판투스 방정식의 해를 계산할 때 확장 유클리드 알고리즘을 활용할 수 있다. 해들 중 하나를 특수 해(particular solution)라고 하며 나머지를 일반 해(general solution)라고 한다. 확장 유클리드 방정식을 이용하여 특수 해를 구하며, 특수 해를 이용해 일반 해를 구한다.