이동식 저장소

저번 시간까지 RSA에 대해 공부했다. 이제 두 번째 암호에 대해 알아보자. 이산 로그 (Discrete Log) $Z_{n}^{*}=\{ g,g^{2},\cdots,g^{\varphi (n)} (=1) \} $이면 $g$는 $Z_{n}^{*}$의 ``Generator``이다. ``Generator``가 항상 존재하지는 않는다. 예를 들어 $Z_{15}^{*}$의 ``Generator``는 존재하지 않는다. 사실 ``Generator``가 존재할 조건은 다음과 같다. $Z_{n}^{*}$의 ``Generator``가 존재한다 $\Leftrightarrow~n=2,2^{2},p^{k},2p^{k}$, $p$는 홀수 소수 $Z_{7}^{*}=\{1,2,3,4,5,6\}$의 ``Generator`` $g=3$..

소인수분해는 얼마나 어려운가? RSA를 뚫는 것은 $n$을 소인수분해(factoring)하는 문제와 동치임을 보였다. 그러면 소인수분해는 얼마나 어려운가? 지금까지 알려진 바에 의하면 소인수분해는 $NP \cap co-NP$에 속한다. 그러나 소인수분해가 $P$에 속하는지는 알려지지 않았다. 추측하기로는 $P$에는 속하지 않고, $NP \cap co-NP$에 속하지 않을까 싶다. 소인수분해와 소수 확인 (Primality) 더보기 # 소인수분해와 소수 (펼치기) 소인수분해를 하면 소수인지 확인할 수 있다. 그러나 소수인지 아닌지 안다고해서 소인수분해가 가능한 것은 아니다. 소수가 아니라면 그 수의 소인수를 찾아야 하기 때문이다. 위에서 말했듯이 소인수분해는 $P$에 있는지 알려지지 않았다. $n$이 소수..

Complete Residue System $Z_{6}=\{0,1,2,3,4,5\}$에서, $5 \times 5=1 \mod 6$이므로 $5$의 역원은 $5$이다. 그런데 $2$와 곱해서 $1$이 되는 수, 즉 $2$의 역원은 존재하지 않는다. 따라서 Complete Residue System에서는 곱셈이 잘 정의되지 않는다. 곱셈이 잘 정의되지 않는다는 말은 역원 또는 항등원이 존재하지 않는다는 말과 같다. 우리는 곱셈과 나눗셈이 잘 정의되는 Residue System을 원한다. Reduced Residue System $Z_{m}^{*}=\{a|\gcd(a,m)=1,~0 \le a < m\}$ $Z_{m}^{*}$에서 곱셈이 잘 정의된다는 것을 증명한다. $\forall a \in Z_{m}^{*},..

이번주면 정수론은 끝난다. 다음주에는 지금 배우는 내용을 바로 써먹을 수 있는 암호를 공부한다. $a|bc,~\gcd(a,~b)=1 \Rightarrow a|c$ $a$가 $bc$를 나눈다. 그런데 $a$와 $b$의 최대공약수가 $1$이라면 $a$는 $b$를 나누지 못한다. 따라서 $a$가 $c$를 나눠야만 한다. 직관적으로는 당연하지만 한번 증명해 보자. 증명 $a|bc$이므로 $bc=ka$를 만족하는 정수 $k$가 존재한다. 또한 $\gcd(a,~b)=1$이므로 $ax+by=1$을 만족하는 정수 $x,~y$가 존재한다. $ax+by=1$의 양변에 $c$를 곱하면 $acx+bcy=acx+kay=a(cx+ky)=c$이다. $c=k'a$ 꼴로 나타낼 수 있으므로 $a$가 $c$를 나누고, $a|c$이다. ..

개강 8주만에 정수론을 시작한다. 예제 $n$이 음이 아닌 정수일 때, $2^{a}+3^{n}=n!$를 만족하는 음이 아닌 정수 $a,~b$를 찾으시오. $n \ge 2$일 때 $n!$는 짝수이다. 그런데 $2^{a}$는 $a \ge 1$일 때 짝수, $3^{b}$는 모든 $b \ge 0$에 대해 홀수이므로 주어진 방정식은 $a=0$일 때만 해를 가질 수 있다(해가 있는지는 둘째치고). 따라서 $1+3^{b}=n!$을 만족시키는 $b$를 찾자. 계산해보면 $n=2$일 때 $a=b=0$의 해가 존재한다. 이것이 유일한 해일까? $n \ge 3$일 때 $n!$은 $3$의 배수이다. 그런데 $1+3^{b}$는 모든 음이 아닌 정수 $b$에 대해 3의 배수가 아니다. 따라서 주어진 방정식의 해는 $n=2$일 때..