11주차 2차시

소인수분해는 얼마나 어려운가?

RSA를 뚫는 것은 $n$을 소인수분해(factoring)하는 문제와 동치임을 보였다. 그러면 소인수분해는 얼마나 어려운가?

 

지금까지 알려진 바에 의하면 소인수분해는 $NP \cap co-NP$에 속한다. 그러나 소인수분해가 $P$에 속하는지는 알려지지 않았다. 추측하기로는 $P$에는 속하지 않고, $NP \cap co-NP$에 속하지 않을까 싶다.

소인수분해와 소수 확인 (Primality)

# 소인수분해와 소수 (펼치기)

소인수분해를 하면 소수인지 확인할 수 있다. 그러나 소수인지 아닌지 안다고해서 소인수분해가 가능한 것은 아니다. 소수가 아니라면 그 수의 소인수를 찾아야 하기 때문이다.

 

위에서 말했듯이 소인수분해는 $P$에 있는지 알려지지 않았다.

 

• $n$이 소수인가?

수천 년 동안 사람들은 소수인지를 다항 시간에 확인할 수 있는 알고리즘을 찾기 위해 노력했다. 놀랍게도 1990년대에 인도의 학부생이 졸업 논문에서 다항 알고리즘을 제시했다. 

 

하지만 $(\log n)^{20}$짜리 알고리즘이기 때문에 별로 실용적이지는 않다. 어쨌든 소수 문제는 $P$에 속한다는 것이 증명되었다. 하지만 소인수분해가 어디에 속하는지는 여전히 밝혀지지 않았다.

RSA 뒷이야기

• $C=m^{e} \mod n$을 어떻게 계산하지?

$m$도 $n$도 매우 큰 수인데, 가뜩이나 큰 $m$을 $e$번이나 제곱하고 그걸 또 $n$으로 나누라고? 그 전에 $m$을 컴퓨터에 저장할 수나 있을까? 500자리 수는? 1000자리 수는????

 

# 해결법 (펼치기)

1. $m^{e}$를 계속 계산하는 게 아니라, $m$을 한 번 곱할 때마다 나머지를 취하면 된다.

2. 분할 정복을 사용하여 $e$번 곱하는 연산을 $\log e$ 시간에 완료할 수 있다. (관련 문제: 행렬 제곱)

 

• 소수 $p$와 $q$를 어떻게 찾을까?

일단 소수는 무한히 많이 존재한다. 소수가 유한했다면 RSA는 진작에 버려졌을 것이다.

 

그런데 소수는 무한하긴 하지만, 매우 드물게 존재한다. 따라서 쓸만한 소수를 선택하려면 대충 몇천 만 자리까지는 가야 한다. 이쯤 되면 수 하나 저장하는 데에만 기가바이트 단위의 공간을 써야 할 지도 모른다.

 

$[1,~n]$ 구간에는 대략 $\log_{e}{n}$개마다 하나의 소수가 존재한다. 즉 한 2000개 정도 찍으면 소수 몇 개 정도는 얻을 수 있다는 뜻. 그런데 무작위로 찍은 수가 소수인지는 어떻게 알지? 사실 위에서 이미 말하긴 했지만, 더 빠른 방법이 없을까?

소수 판별

$n$이 소수인지 어떻게 알 수 있을까? $\sqrt{n}$까지 나눠보는 방법은 $n$이 커질수록 비효율적이다.

 

페르마의 정리에 의해 $n$이 소수라면 모든 $1<a<n$인 $a$에 대해 $a^{n-1}=1 \mod n$이다. 또, 오일러의 정리에 의해 임의의 $n$에 대해 $1<a<n$이고 $\gcd(a,n)=1$이라면 $a^{\varphi(n)}=1 \mod n$이다.

 

페르마의 정리에서, 만약 $n$이 소수가 아니라면 $a^{n-1} \ne 1 \mod n~(1<a<n)$일 수도 있지 않을까? 이것은 증명된 것은 아니며, 그냥 믿음 내지는 희망사항일 뿐이다.

 

작은 $n$에 대해 테스트해 보자. $n=8377$이면 $a^{8376}=1 \mod 8377$을 만족하는 $a=35$가 존재한다. 사실 8377은 소수이긴 한데, 어쨌든 나머지가 계속 1이 나오면 ``소수가 아닐까?`` 라고 의심을 해도 좋다는 뜻이다.

 

이번에는 $n=8379$를 생각해 보자. $35^{8378}=2989 \mod 8379$이므로 8379는 소수가 아니다. 즉 35는 8379가 소수가 아니라는 증거 내지는 힌트가 된다.

 

그럼 이 방법을 실제로 사용할 수 있을까? 소수가 아닌 모든 자연수 $n$에 대해 $n$이 소수가 아니라는 증거가 있었으면 좋겠지만, 불행히도 그렇지 않다. ``Carmichael Numbers(카마이클 수)``가 예외이다. ``Carmichael Numbers``란 모든 $1<a<c$에 대해 $a^{c-1}=1 \mod c$를 만족하는 소수가 아닌 자연수 $c$이다.

 

증거가 존재하긴 하지만 매우 드물게 존재한다면 어떨까? 이러면 증거를 찾기 힘들어진다. 무작위로 찍는 방법 외에 증거를 찾는 뾰족한 수가 없기 때문이다. 하지만 다행히도 증거는 많이 존재한다. 만약 $n$이 소수가 아니라는 증거가 적어도 하나 존재한다면, $Z_{n}^{*}$ 중 적어도 절반은 증거임을 보일 수 있다. 즉 증거는 (존재한다면) 많이 존재하거나, 아예 없거나 둘 중 하나라는 뜻이다.

증명

$n$이 소수가 아니라는 증거 중 하나를 $a$라고 하자. $Z_{n}^{*}$을 증거의 집합 $A$와 증거가 아닌 집합 $B$로 나눌 때, $|A| \ge |B|$임을 보일 수 있다.

 

$a \in A$라 하면 $a^{n-1} \ne 1 \mod n$이다. 그러면 $aB$의 모든 원소는 증거이다. $b \in B$에 대해 $(ab)^{n-1}=a^{n-1}b^{n-1}=a^{n-1} \ne 1 \mod n$이기 때문이다. 따라서 $A$에는 최소한 $|B|$개의 원소가 존재한다.

 

따라서 다음의 과정을 통해 소수를 찾을 수 있다.

1. 임의의 수 $n$을 취한다.
2. $n$이 카마이클 수라면 1번으로 돌아간다.
3. $1<a<n$인 임의의 $a$를 고른다.
4. 만약 $\gcd(a,n) \ne 1$이라면 $n$은 소수가 아니므로 1번 과정으로 돌아간다.
5. 만약 $a^{n-1} \ne 1 \mod n$이라면 $n$은 소수가 아니므로 1번 과정으로 돌아간다. 아니라면 3번 과정으로 돌아가서 또다른 $a$에 대해 검사해 본다.

만약 5번 단계의 검사를 $k$번 통과했다면, $n$이 소수가 아닐 확률은 기껏해야 $\frac{1}{2^{k}}$이다. 이 방법을 밀러-라빈 테스트라고 부르는데, 실제로는 이것보다 더 빠른 Solovay-Strassen 방법을 사용한다.