[암호학] Basic Operations

도입

정수론에서는 곱셈, 나눗셈, 나머지 연산을 매우 중요하게 생각한다. 정수론은 지금까지 많이 연구되어왔지만 덧셈이나 뺄셈과 같은 연산자에서는 특이한 성질을 많이 발견하지 못했지만 나머지와 곱셈에서는 특이한 성질들이 많이 발견되어왔기 때문이다.

 

1. Definition about Operations

1.1. Two type of Division

Division; 나눗셈은 크게 2가지 종류가 있다.
정수 나눗셈은 "몫"과 "나머지"를 가지는 결과를 만들어내는 나눗셈이며, 실수 나눗셈은그 결과로 실수값이 나타나며 나머지를 가지지 않는 연산이다.

정수 나눗셈은 보통 다음과같이 표현한다.
$b$를 $a$로 나누었을 때,
$$b=qa+r,\quad 0 \le r < |a|$$

1.2. Divisor and Multiple

$a$ divides $b$는 다음과 같이 표현한다.
$$a|b$$

• $a$가 $b$를 나누어 떨어진다. <Divisibility>
• $b$를 $a$로 나누면 나머지; Reminder가 0이다.
• $a$가 $b$의 약수; Divisor이다.
• $b$가 $a$의 배수; Multiple이다.

1.3. prime

$1, -1, -p, p$로만 나누어 떨어지는 숫자 (1은 제외한다.)

 

2. Property

2.1. Some property

The following hold

Property 1 : 1, 0

• $1|a$ : 1은 모든 수를 나누어 떨어진다.
• $-1|a$ : -1은 모든 수를 나누어 떨어진다.
• $a|0$ : 0은 모든 수로 나누어 떨어진다.

Property 2 : 자기자신

• $a|a$ : a는 자기자신을 나누어 떨어진다.
• $a|-a$ : a는 -a를 나누어 떨어진다.
• $-a|a$ : -a는 a를 나누어 떨어진다.
• $-a|-a$ : -a는 자기자신을 나누어 떨어진다.

Property 3 : 덧셈

$a$가 $b$와 $c$의 공약수이면, $bx+cy$를 나누어 떨어진다.
$$a|b \ \text{and}\ a|c,\ \text{then} \ a|(bx+cy)$$

Property 4 : 약수의 약수

$a$가 $b$를 나누어 떨어지 $b$가 $c$를 나누어 떨어지면, $a$는 $c$를 나누어 떨어진다.
$$a|b \ \text{and}\ b|c,\ \text{then} \ a|c$$

2.2 proof

Tip $a|b$ 임을 보이려면, $b=ca$를 만족하는 어떤 $c$가 존재하는 것을 보이면 된다.
$$b=ca$$

Proof about Property 1 : 1, 0

• $a=c\times 1$이 되게하는 어떤 $c=a$가 항상 존재한다.$\Box$
• $a=c\times -1$이 되게하는 어떤 $c=-a$가 항상 존재한다.$\Box$
• $0 = c \times a$가 되게하는 어떤 $c=0$가 항상존재한다.$\Box$

Proof about Property 2 : 자기자신

• $a=c\times a$가 되게하는 어떤 $c=1$이 항상 존재한다.$\Box$
• $-a=c\times a$가 되게하는 어떤 $c=-1$이 항상 존재한다.$\Box$
• $a=c\times -a$가 되게하는 어떤 $c=-1$이 항상 존재한다.$\Box$
• $-a=c\times -a$가 되게하는 어떤 $c=1$이 항상 존재한다.$\Box$

Proof about Property 3

덧셈가정 2가지로 부터 다음을 얻을 수 있다.

• $a|b$로부터 $b=sa$ 임을 알 수 있다.
• $a|c$로부터 $c=ta$임을 알 수 있다.

$bx+cy$에 대해 가정으로부터 얻은 수식을 대입하면, 다음과 같이 표현할 수 있다.
$$sax+tay = a(sx+ty)$$
즉, $bx+cy$는 $a$의 배수이므로 $a$로 나누어 떨어진다. $\Box$

Proof about Property 4 : 공약수

가정 2가지로 부터 다음을 얻을 수 있다.

• $a|b$로부터 $b=sa$ 임을 알 수 있다. $(1)$
• $b|c$로부터 $c=tb$임을 알 수 있다. $(2)$

$c$에 대한 표현식($\text{Eq 2}$)에 존재하는 $b$에 가정으로부터 얻은 $b$에 대한 수식($\text{Eq 1}$)을 대입하면, 다음과 같이 표현할 수 있다.
$$c = tsa = a(ts)$$
즉, $c$는 $a$의 배수이므로 $a$로 나누어 떨어진다. $\Box$

 

 

3. Division Theorem[^1]

3.1. Division Theorem

Theorem 1 For integers $(a\ne0)$, there exist unique integers $q$ and $r$ such that,
$$b=qa+r,\ 0\le r < |a|$$

 

3.2. Proof about Division Theorem

다음과 같이 $b$를 $a$로 나누었을 때 여러 개의 몫, 나머지 $q_1, q_2, r_1, r_2$가 있다고 가정하자. (귀류법)

$$\begin{align} b &= q_1a+r_1 \\ b &= q_2a+r_2 \end{align}$$

 

나머지가 같은 경우에는 반드시 몫도 동일하다는 것을 보이는 과정(1), 나머지가 다른 경우에는 모순이 발생함을 보이는 과정(2)에 따라 증명을 진행한다.

 

case1) 만약 $r_1=r_2$이면, 반드시 $q_1 = q_2$가 된다.
Eq 1과 2는 모두 $b$에 대한 식이기 때문에, 두 식의 우변이 같다. 따라서 두 나머지가 동일하면 $r_1 = r_2$이기 떄문에 소거될 수 있어서 다음과 같이 표현된다.

$$\begin{align} q_1a &= q_2a \\ (q_1 - q_2)a &= 0\end{align}$$
$a$는 0이 아닌 정수이기 때문에 $(q_1-q_2)$가 $0$이 되어야하며, 따라서 $q_1 = q_2$가 된다.

 

case2) 만약 $r_1 \ne r_2$인 경우 모순이 발생해서는 안된다.
두 나머지 중에서 더 큰 수를 $r_2$라고 하자. ($r_2 > r_2$)
나머지 $r$은 $|a|$보다 더 클 수 없기 때문에, 다음의 식이 성립해야한다.
$$0 < r_2 - r_1 < a$$ Eq 1과 2를 사용해서 식을 정립하면 다음과 같이 표현할 수 있다.

Eq 3을 보면, 좌변은 $a$의 배수이기 때문에 $a$로 나눈 나머지가 항상 $0$이지만 우변은 $a$보다 작은 범위에 있어서 절대 $a$의 배수가 될 수 없기 때문에 나머지가 $0$이 될 수 없다.

즉, 양변을 동일한 수로 나눈 나머지가 다르기 때문에 모순이 발생한다. 따라서 모순이 발생했기 때문에 가정이 틀렸다. 따라서 몫과 나머지 $q, r$은 유일하다.$\Box$

 

[^1]: Division Theorem은 정수 나눗셈 뿐만 아니라 실수 나눗셈에서도 성립한다. 즉, 실수 나눗셈 결과로서 얻게 되는 결과가 유일하다.