소수 판별하기

우리가 컴퓨터에서 합당한 시간안에 결과를 찾을 수 있는 것은 과연 어느정도의 시간일까라는 생각을 많이 해봅니다.

암호학이라고 한다면, 적어도 100년?  아니면 그 이상일 수도 있겠다는 생각도 하죠.

주어진 수가 소수인지 아닌지, 판별하는 방법은 고전적인 방법에서부터 정수론에 기초한 방법까지 다양하게 있습니다.

소수판별법은 암호학에서 아주 중요합니다.  실제 소수판별을 쉽게 하는 방법이 있다면, 암호 해독도 더 쉬워집니다.

제일먼저 유클리드 호제법을 응용한 방법입니다.

[유클리드 호제법을 이용한 소수 판별]

bool isPrimeBF(_int64 n)
{
	if( n%2 == 0 ) return false;

	for( unsigned __int64 r = 3 ; r*r <= n ; r += 2 )
		if( n%r == 0 ) return false;
	return true;
}

이 알고리즘은 아주 단순한 방법입니다.  소수의 정의를 100% 사용한 알고리즘이죠.

이 알고리즘의 점근적 복잡도는 입니다.

주어진 숫자가 10000 근방이라면, 100번정도 수행하면 된다는 이야기죠.

그런데, 숫자가 10자리라면, 100,000번 정도 수행하면 됩니다.  이정도면 왠만한 컴퓨터에서는 1초도 안 되는 시간안에 답을 낼 수가 있습니다.

숫자가 100자리라면, 1초에 1억번 수행할 수 있는 컴퓨터라면, 1년 365일 24시간 풀가동을 시킨다 해도.. 3,000,000,000,000,000,000,000,000,000,000,000,000년 이상이 걸립니다.

이정도 시간이면, 우주의 나이보다 더 길죠.  우주의 나이는 137억년정도라고 예측하는데요.

정수론에 기초를 둔 밀러-라빈 방법을 이용한다면 보다 나은 시간안에 정수를 판별할 수 있습니다.  밀러-라빈 방법은 아주 큰 수에 대해서는 확률론에 기초해서 소수판별이 완벽하지 않을 수 있습니다만, 현실적으로 꽤 큰 수에 대해서는 횟수를 줄여서 할 수 있습니다.

[밀러-라빈법을 이용한 소수 판별]

//	Miller-Rabin primality test
bool isPrimeMR(_int64 n)
{
	int a[] = { 2, 3, 5, 7, 11, 13, 17, 19, 0 };
	int s = 0;
	unsigned unsigned __int64 n1 = n-1;
	int v = 0;

	for( s = 0 ; !(n1&1) ; s++, n1>>=1 ) ;

	for( int i = 0 ; i < 64 ; i++ )
		if( (n1>>i)&1 ) v = i;

	for( int i = 0 ; a[i] > 0 && a[i] < n ; i++ )
		if( testPrime(n, s, n1, v, a[i]) == false ) return false;

	return true;
}

bool testPrime(unsigned __int64 n, int s, unsigned __int64 d, int v, int a)
{
	unsigned __int64 ad = 1;
	unsigned __int64 an[64];
	int i;

	for( an[0] = a, i = 1 ; i <= v ; i++ )
		an[i] = MultiplyAndMod(an[i-1], an[i-1], n);

	for( ad = 1, i = 0 ; i <= v ; i++ )
		if( (d>>i)&1 ) ad = MultiplyAndMod(ad, an[i], n);

	if( ad == 1 || ad == n-1 ) return true;

	for( i = 1 ; i < s ; i++ )
	{
		ad = MultiplyAndMod(ad, ad, n);
		if( ad == n-1 ) return true;
	}

	return false;
}

이 알고리즘은 입니다.  더 낮출 수가 있지만, 일단은 이정도로 생각하면 됩니다.

주어진 숫자가 10자리라면, 36,175 번에 비례하는 정도의 연산횟수가 필요합니다.  오히려 전자의 방법보다 연산하는 반복 횟수는 줄었지만, 더 오랜 시간이 소요됩니다.

그렇지만, 알고리즘의 효율 차이는 숫자가 커질 때 나타납니다.

숫자가 100자리라면... 밀러-라빈법에 기초하면, 36,175,796 번에 비례하는 정도의 연산횟수가 필요합니다.  

실제 숫자 자릿수별로, 두 알고리즘을 만번 돌렸을 때 결과를 보면,

이 나옵니다.

해당 자릿수의 만개의 홀수 중, 소수의 갯수를 표시한 것과, 수행시간을 초로 표시해보았습니다.  앞에것이 첫번째 방법, 뒤에것이 두번째 방법입니다.  앞에 것 수행시간을 보면, 자리수가 2씩 증가할 때마다, 약 10배씩 상승한 것을 볼 수 있습니다.  뒤에것은 서서히 변하는 것을 볼 수 있고요.  위 결과를 토대로 본다면, 20자리숫자는 16000 초 정도 소요되겠죠.  결국 소수 하나 판별하는데 걸리는 시간은 1.6초가 걸립니다.  100자리수라면.. 아.. 상상도 하기 싫군요.

당연히 암호학에서는 두번째 방법을 씁니다.  보다 빠른 알고리즘을 개발하는 것이 중요하죠.

공개키 알고리즘에서 500비트정도의 소수를 쓰는데, 이럴경우 십진수로는 150자리정도 됩니다.  공개키에서 소수판별이 필요한데, 유클리드 방법을 쓰면, 20자리숫자가 1초 넘게 걸리는데, 150자릿수는 아마 몇년.. 몇십년?? 몇백년??? 계산을 안 해봐서 모르겠네요.