[암호학] 1. 기초 정수론(1)

[암호학] 1. 기초 정수론(1)

정수 전체의 집합을 $\mathbb{Z}$로 나타내고 그 원소는 다음과 같다. $$\mathbb{Z}=\{\cdots,\,-2,\,-1,\,0,\,1,\,2,\,\cdots\}$$ (나눗셈 알고리즘, divisor algorithm) 임의의 $a,\,b\in\mathbb{Z}\,(b\neq0)$에 대하여 $$a=bq+r,\,0\leq r<|b|$$ 인 정수 $q,\,r$이 유일하게 존재하고, 이것을 각각 $a$를 $b$로 나누었을 때의 몫(quotient), 나머지(remain)라고 한다.   

두 $a,\,b\in\mathbb{Z}$에 대하여 적당한 $c\in\mathbb{Z}$가 존재해서 $b=ac$이면, $a$를 $b$의 약수(divisor) 또는 인수(factor)라 하고, $b$를 $a$의 배수(multiple)라 하며, 이것을 $a|b$로 나타낸다. 또한 정수 $a$에 대하여 $a$의 배수 전체의 집합을 $a\mathbb{Z}=\{ax\,|\,x\in\mathbb{Z}\}$로 나타낸다. 

두 정수 $a,\,b$에 대하여 다음의 두 조건을 만족하는 양의 정수 $d$를 $a,\,b$의 최대공약수(greatest common divisor)라고 하고, 이것을 $d=\text{gcd}(a,\,b)$로 나타낸다.

(a) $d|a$이고 $d|b$

(b) $c|a$이고 $c|b$이면 $c\leq d$

이때 적당한 $x,\,y\in\mathbb{Z}$가 존재해서 $\text{gcd}(a,\,b)=ax+by$이다.

두 정수 $a,\,b$에 대하여 다음의 두 조건을 만족하는 양의 정수 $l$을 $a,\,b$의 최소공배수(least common multiple)라 하고, 이것을 $m=\text{lcm}(a,\,b)$로 나타낸다.

(a) $a|m$이고 $b|m$

(b) $c>0$일 때 $a|c$이고 $b|c$이면, $m\leq c$  

네 정수 $a,\,b,\,q,\,c$가 주어졌을 때 $a=bq+c$이면 $\text{gcd}(a,\,b)=\text{gcd}(b,\,c)$이다. 

유클리드 알고리즘(Euclidean algorithm) 두 양의 정수 $a,\,b$에 대하여. 나눗셈 알고리즘에 의해 다음이 성립한다. $$\begin{align*}a&=q_{1}b+r_{1}\,0<r_{1}<b\\b&=q_{2}r_{1}+r_{2}\,0<r_{2}<r_{1}\\r_{1}&=q_{3}r_{2}+r_{2}\,0<r_{3}<r_{2}\\ \,&\vdots\\r_{n-2}&=q_{n}r_{n-1}+r_{n}\,0<r_{n}<r_{n-1}\\r_{n-1}&=q_{n+1}r_{n}+0\end{align*}$$ 또한 $$\text{gcd}(a,\,b)=\text{gcd}(b,\,r_{1})=\cdots=\text{gcd}(r_{n-1},\,r_{n})=\text{gcd}(r_{n},\,0)=r_{n}$$ 이므로 $r_{n}$이 $a,\,b$의 최대공약수이다. 

두 정수 $a,\,b$의 최대공약수가 1일 때, 즉 $\text{gcd}(a,\,b)=1$일 때 $a$와 $b$는 서로소(relative prime)라고 한다. 

두 정수 $a,\,b$에 대해 $\text{gcd}(a,\,b)=1$일 필요충분조건은 $x,\,y\in\mathbb{Z}$가 존재해서 $ax+by=1$이 성립하는 것이다.    

 

정수 $a_{1},\,...,\,a_{n}$과 $m$에 대하여 다음이 성립한다.

(a) $\text{gcd}(ab,\,m)=1$일 필요충분조건은 $\text{gcd}(a,\,m)=\text{gcd}(b,\,m)=1$

(b) $\text{gcd}(a_{1}\cdots a_{n},\,m)=1$일 필요충분조건은 $\text{gcd}(a_{1},\,m)=\cdots\text{gcd}(a_{n},\,m)=1$이다. 

(c) $\text{gcd}(a,\,b)=1$일 필요충분조건은 $\text{gcd}(a^{n},\,b)=1$이고, $\text{gcd}(a,\,b)=1$일 필요충분조건은 $\text{gcd}(a,\,b^{n})=1$이다. 

2 이상의 정수 $p$의 약수가 1과 $p$ 뿐이면, $p$를 소수(prime)라 하고, 1보다 큰 정수 $n$이 소수가 아니면, 즉 정수 $d,\,e$가 존재해서 $n=de$이면, $n$을 합성수(composite number)라고 한다. 

$p$가 소수일 때 두 정수 $a,\,b$에 대하여 $p|ab$이면, $p|a$ 또는 $p|b$이다. 

산술의 기본정리(fundamental theorem of arithmetic) 1 이상의 양의 정수 $n$은 소수이거나 합성수이고, 그 표현은 유일하다. 임의의 정수 $n$을 다음과 같이 나타낼 수 있고 $$n=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{r}^{e_{r}}$$ 여기서 $p_{1},\,p_{2},\,\cdots,\,p_{r}$는 서로 다른 소수이고, 이것을 $n$의 표준분해라고 한다.

양의 정수 $n$에 대해 $\tau(n)$을 $n$의 양의 약수 전체의 개수, $\sigma(n)$을 $n$의 양의 약수 전체의 합으로 정의한다. 이러한 함수를 정수론적 함수(number-theoric function)라고 한다. 정수 $n$의 표준분해가 $n=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{n}^{e_{n}}$일 때 $\tau(n)$과 $\sigma(n)$은 다음과 같다. $$\begin{align*}\tau(n)&=(e_{1}+1)(e_{2}+1)\cdots(e_{n}+1)\\ \sigma(n)&=(1+p_{1}+\cdots+p_{1}^{e_{1}})(1+p_{2}+\cdots+p_{2}^{e_{2}})\cdots(1+p_{r}+\cdots+p_{r}^{e_{r}})\\&=\frac{p_{1}^{e_{1}+1}-1}{p_{1}-1}\frac{p_{2}^{e_{2}+1}-1}{p_{2}-1}\cdots\frac{p_{r}^{e_{r}+1}-1}{p_{r}-1}\end{align*}$$ 임의의 실수 $x$에 대해 $[x]$를 $x$보다 크지 않은 최대 정수로, $\{x\}=x-[x]$로 정의한다. 여기서 $[x]$와 $\{x\}$를 각각 $x$의 정수부분, 소수부분이라고 한다. 

$x$보다 크거나 같은 정수 중 가장 작은 정수를 $\lceil x\rceil$로 나타내고 이 정수를 $x$의 최고한도(ceiling), $[x]$를 $\lfloor x\rfloor$로 나타내고 이것을 $x$의 최저한도(floor)라고 한다. 

정수 $F_{n}=2^{2^{n}}+1\,(n\geq0)$을 페르마 수(Fermat number)라 하고, $F_{n}$이 소수이면, 이 수를 페르마 소수(Fermat prime)라고 한다. 또한 정수 $M_{p}=2^{p}-1\,(m\geq1)$을 메르센 수(Mersenne number)라 하고, $M_{p}$가 소수일 때 이 수를 메르센 소수(Mersenne prime)라고 한다. 

$n$을 고정된 정수라고 하자. 두 정수 $a,\,n$가 법 $n$에 대해 합동(congruent), 즉 $$a\equiv b\,(\text{mod}\,n)$$ 이라는 것은 $a-b$가 $n$의 배수, 즉 적당한 $k\in\mathbb{Z}$가 존재해서 $a-b=kn$인 것이다. 

$n>1$을 고정된 정수, $a,\,b,\,c,\,d$를 임의의 정수라 하자. 그러면 다음이 성립한다. 

(a) $a\equiv a\,(\text{mod}\,n)$ 

(b) $a\equiv b\,(\text{mod}\,n)$이면, $b\equiv a\,(\text{mod}\,n)$이다.  

(c) $a\equiv b\,(\text{mod}\,n)$이고 $b\equiv c\,(\text{mod}\,n)$이면, $a\equiv c\,(\text{mod}\,n)$이다.  

(d) $a\equiv b\,(\text{mod}\,n)$이고 $c\equiv d\,(\text{mod}\,n)$이면, $a+c\equiv b+d\,(\text{mod}\,n)$이고 $ac\equiv bd\,(\text{mod}\,n)$이다. 

(e) $a\equiv b\,(\text{mod}\,n)$이면 $a+c\equiv b+c\,(\text{mod}\,n)$이고, $ac\equiv bc\,(\text{mod}\,n)$이다. 

(f) $a\equiv b\,(\text{mod}\,n)$이면 $a^{k}\equiv b^{k}\,(\text{mod}\,n)\,(k>0)$이다.  

$ca\equiv cb\,(\text{mod}\,n)$이면, $\displaystyle a\equiv b\,\left(\text{mod}\,\frac{n}{d}\right)\,(d=\text{gcd}(c,\,n))$이다. 

     

선형합동식 $ax\equiv b\,(\text{mod}\,n)$이 해를 가질 필요충분조건은 $d|b\,(d=\text{gcd}(a,\,n))$가 성립하는 것이고, $d|b$이면, 이 선형합동식은 $d$개의 법 $n$에 대해 서로 다른 해를 갖는다. 이 선형합동식의 하나의 해가 $x_{0}$이면, $d$개의 해는 다음과 같다. $$x_{0},\,x_{0}+\frac{n}{d},\,x_{0}+2\frac{n}{d},\,...,\,x_{0}+(d-1)\frac{n}{d}$$ $\text{gcd}(a,\,n)=1$이면, 선형합동식 $ax\equiv b\,(\text{mod}\,n)$은 하나의 해를 갖고 적당한 정수 $s,\,t$에 대하여 $as+nt=1$이고 $a(sb)+n(tb)=b$, 즉 $a(sb)\equiv b\,(\text{mod}\,n)$이므로 $x\equiv sb\,(\text{mod}\,n)$은 합동식 $ax\equiv b\,(\text{mod}\,n)$의 유일한 해이다.

중국인의 나머지 정리(Chinese remainder theorem) $n_{1},\,n_{2},\,...,\,n_{r}$을 양의 정수로 $i\neq j$에 대해 $\text{gcd}(n_{i},\,n_{j})=1$이라 하자. 그러면 다음의 연립 선형합동식들은 해를 갖고 $$\begin{align*}x&\equiv a_{1}\,(\text{mod}\,n_{1})\\x&\equiv a_{2}\,(\text{mod}\,n_{2})\\ \,&\vdots\\x&\equiv a_{r}\,(\text{mod}\,n_{r})\end{align*}$$ 그 해는 법 $n_{1}n_{2}\cdots n_{r}$에 대해 유일한 해를 갖는다. $n=n_{1}n_{2}\cdots n_{r}$이라 할 때 $$N_{i}=\frac{n}{n_{i}}=n_{1}\cdots n_{i-1}n_{i+1}\cdots n_{r},\,N_{i}x_{i}\equiv1\,(\text{mod}\,n_{i})$$ 라 하고 $$u=a_{1}N_{1}x_{1}+\cdots+a_{r}N_{r}x_{r}$$ 이라 하면 이 현립 선형합동식의 해를 $x\equiv u\,(\text{mod}\,n_{1}n_{2}\cdots n_{r})$로 나타낼 수 있다.

다음의 연립 선형합동방정식 $$\begin{align*}ax+by&\equiv r\,(\text{mod}\,n)\\cx+dy&\equiv s\,(\text{mod}\,n)\end{align*}$$ 은 $\text{gcd}(ad-bc,\,n)=1$일 때 법 $n$에 대한 유일한 해를 갖고, 그 해는 다음과 같다. $$\begin{align*}x&\equiv t(dr-bs)\,(\text{mod}\,n)\\y&\equiv t(as-cr)\,(\text{mod}\,n)\end{align*}$$ 페르마 정리(Fermat's theorem) $p$를 소수 $p\not|a$라 하자. 그러면 $a^{p-1}\equiv1\,(\text{mod}\,p)$이다. 

양의 정수 $n$에 대해 $\mathbb{Z}_{n}=\{0,\,1,\,...,\,n-1\}$이라 하자. $\mathbb{Z}_{n}$의 원소 중 $n$과 서로소인 원소들의 집합을 $\mathbb{Z}_{n}^{*}$라 하자. $\mathbb{Z}_{n}^{*}=\{r\in\mathbb{Z}_{n}\,|\,\text{gcd}(r,\,n)=1\}$의 원소의 개수 $\phi(n)$을 오일러-$\phi$ 함수(Euler $\phi$ function)라고 한다. 

정수 $n$의 표준분해가 $n=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{r}^{e_{r}}$이면 다음이 성립한다. $$\begin{align*}\phi(n)&=n\left(1-\frac{1}{p_{1}}\right)\left(1-\frac{1}{p_{2}}\right)\cdots\left(1-\frac{1}{p_{r}}\right)\\&=(p_{1}^{e_{1}}-p_{1}^{e_{1}-1})(p_{2}^{e_{2}}-p_{2}^{e_{2}-1})\cdots(p_{r}^{e_{r}}-p_{r}^{e_{r}-1})\end{align*}$$ 또한 서로소인 $m,\,n$에 대하여 $\phi(mn)=\phi(m)\phi(n)$이다.  

오일러 정리(Euler theorem) $n$을 양의 정수, $\text{gcd}(a,\,n)=1$이라 하자. 그러면 $a^{\phi(n)}\equiv1\,(\text{mod}\,n)$이다. 

$b\equiv a^{k}\,(\text{mod}\,n),\,(0\leq b<n)$인 정수 $b$의 계산:

(a) 시작: $b=1$이라 한다.

(b) 계산완료: $k=0$이면 $b$로 돌아와서 계산을 끝낸다. 

(c) $k$가 홀수이면 $$c\equiv b\cdot a\,(\text{mod}\,n),\,0\leq c<n$$ 인 정수 $c$를 새로 $b$로 놓고 $k-1$을 새로 $k$로 놓아 단계 (2)로 간다. 

(d) $k$가 짝수이면 $$c\equiv a^{2}\,(\text{mod}\,n),\,0\leq c<n$$ 인 정수 $c$를 새로 $a$로 놓고 $\displaystyle\frac{k}{2}$를 새로 $k$로 놓아 (2)로 간다. 

참고자료:

암호학과 부호이론, 박승안, 경문사

Elementary Number Theory 7th edition, Burton, McGraw-Hill