[암호학] 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