2.15. 소수(Prime Number)
소수는 1과 그 자신만을 약수로 가지는 1보다 큰 자연수이다. 예를 들어, 1,3,5,7,11,17,19... 이런 수들이다. 소수는 암호학에서 비대칭키 알고리즘으로 현재까지 가장 많이 사용되고 있는 RSA암호의 근간이 되는 수이다.
자연수가 무수히 많듯이 소수도 무한히 많다. 수학적으로 증명이 된 사실이다.
수학자 유클리드가 증명한 방법은 다음과 같다.
유한 개의 소수가 존재한다고 가정하자.
이 유한 개의 소수들을 모두 곱한 값에 1을 더한다. (유클리드 수 참조)
그 결과값은 다른 어떤 소수로 나누어도 나머지가 1이므로 어떤 소수로도 나누어 떨어지지 않는 수가 된다.
따라서 이 수가 소수라면 기존의 최대소수보다 큰 소수가 있다는 것이 증명되고, 이 수가 소수가 아니라고 해도 기존의 최대소수보다 큰 소수가 있어야 한다는것을 의미하기 때문에 소수가 유한하다는 애초 가정에 모순이 존재함을 알 수 있다.
어떤 수가 있을 때 소수인지를 어떻게 판단할까?
가장 간단한 방법은 그리스 수학자인 에라토스테네스의 체(뭔가를 걸러내는 체)라는 방법이다.
방법은 이렇다.
에라토스테네스의 체를 이용해서 자연수 n까지에 존재하는 소수 구하기
1) 2에서 부터 시작해서 n까지의 수에서, 2의 배수인 수를 없앤다. 2,4,6,8...같은 수들이 없어진다.
2) 1번에 의해 없어지지 않고 남은 수 중에서 가장 작은 수, 즉 3보다 큰 수에 대해서 3의 배수가 되는 수들을 없앤다. 3,9,12... 이런 수들이 없어질 것이다. (6은 3의 배수이지만, 2의 배수이기도 해서 이미 1번에 의해 없어졌다)
3)1과 2번에 의해 없어지고 난 다음 남은 수 중에서 가장 작은 수는 이제 5이다. 이 5보다 큰 수 중에서 5의 배수가 되는 모든 수를 없앤다. 25, 35, 55... 같은 수들이 없어진다.
4)이렇게 계속해서 n에 이르기까지 지우기를 계속해서, 끝까지 남은 수들이 n보다 작은 소수이다. 2,3,5,7,11,13,17,19... 등이 될 것이다.
어떤 수 p가 소수인지 아닌지를 에라토스테네스의 체를 이용해서 알아내려면, p의 크기가 커짐에 따라 연산횟수가 많아진다. 따라서, 암호학에서 사용되는 1024비트 이상의 큰 수에 대해서는 너무 많은 시간이 소요되는 방법이다.
에라토스테네스의 체 말고도, 어떤 수가 소수인지 아닌지를 알아내는 여러가지 알고리즘이 존재한다.
여기서는 큰 수에 대해서도 효율적으로 소수를 판정해내는 Rabin-Miller방식에 대해 소개하고 구현해보도록 하겠다.
Rabin-Miller방식에서 사용되는 가장 기본적인 원리는 '페르마의 작은 정리'이다.
페르마의 작은 정리(Fermet's Little Theorem)
p가 소수이고 a를 p의 배수가 아닌 자연수라 할 때, 즉, gcd(a,p)=1임이 성립할 때 다음 식이 성립한다.
a p-1 ≡ 1 mod p
Rabin-Miller에 의한 소수판정방법
어떤 수 n이 주어질 때 Rabin-Miller에 의한 소수판정 방법은 다음과 같다.
단계 1. n-1를 2로 나누어질 때까지 나누어, n–1 = 2sd 를 만족하는 s와 d을 구함
단계 2. a < n인 a를 임의로 선택함
단계 3. z = as mod n를 계산함
단계 4. z = 1이면 n은 테스트를 통과함. 즉, 소수
단계 5. for i = 0 to s-1 do
if(z = n–1) -> 테스트 통과
else z := z2 mod n
Rabin-Miller 소수판정법을 실제 수를 예로들어 살펴보자.
먼저, 소수인 41을 가지고 판정법에 대입해보자.
n=41
n-1=40
s=3 ; n-1 = 40 = (101000)2 = 23 x 5
d=5
n-1 = 2sd 가 되는 s와 d를 구하는 것은, n-1을 2로 나눌 수 없을 때까지 구하는 것으로, 이것은 2진수로 표현했을 때 오른쪽으로 하나씩 shift하면서 제일 끝자리가 1이 될 때까지 이동하는 것을 말한다. 즉, 40은 이진수로 101000이고 이는 3번 이동했을 때 제일 오른쪽 자리가 1이 되므로, 23 x 5가 된다.
n보다 작은 임의수 a는 2에서 40까지의 수이고, 이 z=as mod n과 z := z2 mod n을 계속해서 구해보면 아래표와 같이 된다.
| a | a^d | z=a^d mod n | z0=z^2 mod n | z1 | z2 |
| 2 | 32 | 32 | 40 | 1 | 1 |
| 3 | 243 | 38 | 9 | 40 | 1 |
| 4 | 1024 | 40 | 1 | 1 | 1 |
| 5 | 3125 | 9 | 40 | 1 | 1 |
| 6 | 7776 | 27 | 32 | 40 | 1 |
| 7 | 16807 | 38 | 9 | 40 | 1 |
| 8 | 32768 | 9 | 40 | 1 | 1 |
| 9 | 59049 | 9 | 40 | 1 | 1 |
| 10 | 100000 | 1 | 1 | 1 | 1 |
| 11 | 161051 | 3 | 9 | 40 | 1 |
| 12 | 248832 | 3 | 9 | 40 | 1 |
| 13 | 371293 | 38 | 9 | 40 | 1 |
| 14 | 537824 | 27 | 32 | 40 | 1 |
| 15 | 759375 | 14 | 32 | 40 | 1 |
| 16 | 1048576 | 1 | 1 | 1 | 1 |
| 17 | 1419857 | 27 | 32 | 40 | 1 |
| 18 | 1889568 | 1 | 1 | 1 | 1 |
| 19 | 2476099 | 27 | 32 | 40 | 1 |
| 20 | 3200000 | 32 | 40 | 1 | 1 |
| 21 | 4084101 | 9 | 40 | 1 | 1 |
| 22 | 5153632 | 14 | 32 | 40 | 1 |
| 23 | 6436343 | 40 | 1 | 1 | 1 |
| 24 | 7962624 | 14 | 32 | 40 | 1 |
| 25 | 9765625 | 40 | 1 | 1 | 1 |
| 26 | 11881376 | 27 | 32 | 40 | 1 |
| 27 | 14348907 | 14 | 32 | 40 | 1 |
| 28 | 17210368 | 3 | 9 | 40 | 1 |
| 29 | 20511149 | 38 | 9 | 40 | 1 |
| 30 | 24300000 | 38 | 9 | 40 | 1 |
| 31 | 28629151 | 40 | 1 | 1 | 1 |
| 32 | 33554432 | 32 | 40 | 1 | 1 |
| 33 | 39135393 | 32 | 40 | 1 | 1 |
| 34 | 45435424 | 3 | 9 | 40 | 1 |
| 35 | 52521875 | 14 | 32 | 40 | 1 |
| 36 | 60466176 | 32 | 40 | 1 | 1 |
| 37 | 69343957 | 1 | 1 | 1 | 1 |
| 38 | 79235168 | 3 | 9 | 40 | 1 |
| 39 | 90224199 | 9 | 40 | 1 | 1 |
처음 계산된 z=as mod n에서 값이 1인 경우는 바로 소수로 판정. 그렇지 않은 경우는 n-1인 40과 같은 지를 보면 되는데, 위 표에서 보듯이 최소한 zs-1내에서 40인 것이 나와서 소수로 판정된다.
만약 소수가 아닌 것에 대해서는 어떻게 소수가 아닌것으로 판정될까?
소수가 아닌 수 49를 예로 해서 보자.
n=49이므로,
n-1=48, s=4, d-3
임의의 수 a에 대해서 각각 계산되는 것을 보면 아래와 같다.
| a | a^d | z=a^d mod n | z0=z^2 mod n | z1 | z2 |
| 2 | 8 | 8 | 15 | 29 | 8 |
| 3 | 27 | 27 | 43 | 36 | 22 |
| 4 | 64 | 15 | 29 | 8 | 15 |
| 5 | 125 | 27 | 43 | 36 | 22 |
| 6 | 216 | 20 | 8 | 15 | 29 |
| 7 | 343 | 0 | 0 | 0 | 0 |
| 8 | 512 | 22 | 43 | 36 | 22 |
| 9 | 729 | 43 | 36 | 22 | 43 |
| 10 | 1000 | 20 | 8 | 15 | 29 |
| 11 | 1331 | 8 | 15 | 29 | 8 |
| 12 | 1728 | 13 | 22 | 43 | 36 |
| 13 | 2197 | 41 | 15 | 29 | 8 |
| 14 | 2744 | 0 | 0 | 0 | 0 |
| 15 | 3375 | 43 | 36 | 22 | 43 |
| 16 | 4096 | 29 | 8 | 15 | 29 |
| 17 | 4913 | 13 | 22 | 43 | 36 |
| 18 | 5832 | 1 | 1 | 1 | 1 |
| 19 | 6859 | 48 | 1 | 1 | 1 |
| 20 | 8000 | 13 | 22 | 43 | 36 |
| 21 | 9261 | 0 | 0 | 0 | 0 |
| 22 | 10648 | 15 | 29 | 8 | 15 |
| 23 | 12167 | 15 | 29 | 8 | 15 |
| 24 | 13824 | 6 | 36 | 22 | 43 |
| 25 | 15625 | 43 | 36 | 22 | 43 |
| 26 | 17576 | 34 | 29 | 8 | 15 |
| 27 | 19683 | 34 | 29 | 8 | 15 |
| 28 | 21952 | 0 | 0 | 0 | 0 |
| 29 | 24389 | 36 | 22 | 43 | 36 |
| 30 | 27000 | 1 | 1 | 1 | 1 |
| 31 | 29791 | 48 | 1 | 1 | 1 |
| 32 | 32768 | 36 | 22 | 43 | 36 |
| 33 | 35937 | 20 | 8 | 15 | 29 |
| 34 | 39304 | 6 | 36 | 22 | 43 |
| 35 | 42875 | 0 | 0 | 0 | 0 |
| 36 | 46656 | 8 | 15 | 29 | 8 |
| 37 | 50653 | 36 | 22 | 43 | 36 |
| 38 | 54872 | 41 | 15 | 29 | 8 |
| 39 | 59319 | 29 | 8 | 15 | 29 |
| 40 | 64000 | 6 | 36 | 22 | 43 |
| 41 | 68921 | 27 | 43 | 36 | 22 |
| 42 | 74088 | 0 | 0 | 0 | 0 |
| 43 | 79507 | 29 | 8 | 15 | 29 |
| 44 | 85184 | 22 | 43 | 36 | 22 |
| 45 | 91125 | 34 | 29 | 8 | 15 |
| 46 | 97336 | 22 | 43 | 36 | 22 |
| 47 | 103823 | 41 | 15 | 29 | 8 |
| 48 | 110592 | 48 | 1 | 1 | 1 |
| 49 | 117649 | 0 | 0 | 0 | 0 |
| 50 | 125000 | 1 | 1 | 1 | 1 |
| 51 | 132651 | 8 | 15 | 29 | 8 |
| 52 | 140608 | 27 | 43 | 36 | 22 |
| 53 | 148877 | 15 | 29 | 8 | 15 |
| 54 | 157464 | 27 | 43 | 36 | 22 |
| 55 | 166375 | 20 | 8 | 15 | 29 |
| 56 | 175616 | 0 | 0 | 0 | 0 |
위 표에서 보다시피, z값이 1과 n-1값이 아니기에 소수가 아닌 것으로 판정될 것이다.
그러나, 중간에 a가 19일 때, 그리고 31일 때에는 z값이 n-1인 48과 같을 때도 있다.
이처럼 이 Rabin-Miller에 의한 소수판정을 어떤 a에 대해서 소수가 아님에도 불구하고 소수처럼 보이게 하는 약점이 있고, 그래서 확률론적 소수판별법이라 부른다. 따라서, 판별하는 횟수를 증가시켜서 다르게 판별할 가능성을 낮춰줘야 한다.
Rabin-Miller판정법에서 소수가 아닌 합성수임에도 불구하고 소수로 판정할 확률은 1/4k라 한다. (여기서 k는 반복 횟수)
따라서, 적절하게 충분히 큰 k 즉, k번 반복해주면 무시할 수준의 에러를 가지면서 빠르게 소수판정을 할 수 있겠다.
Rabin-Miller 소수판정 원리
- n이 소수인데 이 테스트를 통과하지 못하였다고 가정하자.
그러면 am ≠ ±1 (mod n)임 - 또한 이 테스트에서 z는 am, a2m,…,a2k-1m 임
따라서 테스트를 통과하지 못하였으므로 이들 역시 모두 a2im ≠ ±1 (mod n) - n이 소수이고 n-1 = 2km이므로 페르마의 작은 정리에 의해 a2km = 1 (mod n)
- n이 소수이므로 1의제곱근은 1과 -1 밖에 존재하지 않으며,
가정에 의해 a2k-1m ≠ -1 (mod n)이므로 a2k-1m = 1 (mod n)임 - 같은 원리에 의해 a2k-2m, a2k-3m,...,am은 모두 법 n에서 1과 합동이어야 함
- 그런데 am≠ ±1 (mod n) 이므로 이것은 모순임
다음은 위에서 설명한 Rabin-Miller소수판정법 알고리즘을 구현한 소스 및 설명이다.
/************************************************************************** 주어진 BIGINT 값이 소수인지 판정함 Input: @N = 소수인지 판단하려는 BIGINT형 값 @k = reapeating time to check confidence of prime number Output: @returnCode - OK: no error Returns: 소수인지 판단 - 1: 소수 - -1: 소수가 아님 Comment: ***************************************************************************/ int rabin_miller(BIGINT N, int k, int *returnCode){ int prime = 1; int not_prime = -1; BIGINT N_1,A; INT *a; int s; BIGINT D,Z,R; int i,j; INT mask; int exitFlag=-1; int n_bitsLen = bit_length(N); //3이상인것은 보장됨. 2,3이 아니므로 int bitsNum=0; int result; *returnCode = OK;
함수명은 rabin_miller이고, 파라미터 N에 검사할 수와, 몇 번 반복 검사할 지를 k에 넣으면, 성공여부는 *returnCode에 나오고, 함수의 리턴값이 1이면 소수, -1이면 합성수이다.
//0이면 소수아님(-1) 리턴 if(N[0] == 0) return not_prime;
//양수로 바꿔줌 if(isPositive(N) == -1) positive(N);
//짝수이면 소수가 아님 if((N[1] & (INT)0x01) == 0x00) return not_prime;
//2,3인 경우는 소수로 리턴 if(N[0]==1 && (N[1]==2 || N[1]==3)) return prime;
먼저 주어진 수가 0이면 당연히 소수가 아니고, N이 음수이면 양수로 바꿔준다.
N이 짝수이면 소수가 아니고, 간단한 수 2 혹은 3이면 소수로 바로 판정해 준다.
이제 s와 D를 구한다.
//calculate s, D of n-1 = 2^s * D // s: n-1을 2로 나누어 떨어지지 않을 때까지 계속했을 때 값 copy_big(N_1,N); decrese(N_1); s=0; a = N_1 + 1; mask = 0x01; exitFlag = -1; while((a <= (N_1 + SIZE(N_1))) && (exitFlag == -1)){ mask = 0x01; for(i=0;i<(sizeof(INT)*8);i++){ if( (*a & mask) != 0){ exitFlag = 1; break; } mask <<= 1; s++; } } //D: n-1을 2^s로 나눈값 = s만큼 오른쪽 쉬프트한 값 copy_big(D,N_1); shiftright(D,s);
s와 D는 n-1 = 2^s * D를 만족하는 수이다.
따라서, s를 구하는 것은 2로 계속해서 나누다가 자연수로 안놔눠질 때가지를 말하며, 2로 나눈다는 것은 수를 이진수로 표현했을 때 오른쪽으로 하나씩 shift하는 것이므로, n-1값을 오른쪽으로 shift하면서 제일 오른쪽 자리의 비트가 0이 아닐 때까지 얼마만큼 이동했느냐가 s값이 된다.
D는 n-1을, 위에서 구한 s의 거듭제곱으로 나눈 것이고, 이는 n-1값을 오른쪽으로 s만큼 이동시켰을 때 남는 값이 된다.
이제 난수 A를 구하면서 k회만큼 소수인지 판정하자.
//k회만큼 테스트 exitFlag = -1; for(i=0;i<k;i++){ exitFlag = -1; while(exitFlag == -1){ bitsNum = 0; while(bitsNum < 2){ bitsNum = (int)(next_random_float() * n_bitsLen); } //N보다 작은 A생성. bitsNum이 n_bitsLen과 같은 경우 N보다 큰 난수 발생가능성 있음 generate_random(A,bitsNum); if((A[0] == 0) || (A[0]==1 && A[1]==1)){ continue; }else if(compare_big(A,N) == -1){ exitFlag = 1; break; } }
먼저 난수 A를 생성하는데, 이 A는 2이상이고 N이하인 A를 생성한다.
먼저 A가 N의 약수인지 (=공약수가 있는지) 확인한다. 당연히 N이 소수라면 공약수가 없어야 하기에, 만약 공약수가 있다면 N이 소수가 아니라고 판정하고 함수를 벗어난다.
이 부분은 Rabin-Miller의 원래 판정 루틴에는 없으나, 이렇게 gcd를 계산하는 간단한 수고에 의해서 판정 정확도가 더 높아질 수 있겠다.
//생성된 난수 A와 N사이에 최대공약수가 있는지 확인. //이 확인방법은 Rabin-Miller 방법에는 없지만 삽입함 //그럼으로써, gcd판별이라는 적은 공수를 들이고, strong liar한 N을 좀더 빨리 찾아낼 수 있음 gcd(A,N,Z); if(!((Z[0]==1) && (Z[1]==1))){ return not_prime; }
이제 z를 계산하면서 소수판정을 한다.
//z = A^D mod n copy_big(Z,A); mod_exp(Z,D,N,R); //z == 1 or z==n-1 result = -1; if(((Z[0]==1) && (Z[1]==1)) || (compare_big(Z,N_1)==0)){ result = 1; } //s-1회까지 z^2 mod n == (n-1) 인지 확인 for(j=0; (result == -1) && (j<s);j++){ mod_square(Z,N,Z); //1이면 composit if((Z[0]==1) && (Z[1]==1)){ return not_prime; }else if(compare_big(Z,N_1) == 0){ result = 1; break; } } if(result == -1) return not_prime; } return prime; }
z = AD mon n이다.
먼저 이 값이 1 혹은 n-1인지 확인하고, 다시 z = z2 mod n을 해서 n- 1과 같은 지 확인한다.
이러한 과정을 모두 통과해야만 소수로 판정된다.
아래는 전체 소스이다.
/************************************************************************** 주어진 BIGINT 값이 소수인지 판정함 Input: @N = 소수인지 판단하려는 BIGINT형 값 @k = reapeating time to check confidence of prime number Output: @returnCode - OK: no error Returns: 소수인지 판단 - 1: 소수 - -1: 소수가 아님 Comment: ***************************************************************************/ int rabin_miller(BIGINT N, int k, int *returnCode){ int prime = 1; int not_prime = -1; BIGINT N_1,A; INT *a; int s; BIGINT D,Z,R; int i,j; INT mask; int exitFlag=-1; int n_bitsLen = bit_length(N); //3이상인것은 보장됨. 2,3이 아니므로 int bitsNum=0; int result; *returnCode = OK; //0이면 소수아님(-1) 리턴 if(N[0] == 0) return not_prime; //양수로 바꿔줌 if(isPositive(N) == -1) positive(N); //짝수이면 소수가 아님 if((N[1] & (INT)0x01) == 0x00) return not_prime; //2,3인 경우는 소수로 리턴 if(N[0]==1 && (N[1]==2 || N[1]==3)) return prime; //calculate s, D of n-1 = 2^s * D // s: n-1을 2로 나누어 떨어지지 않을 때까지 계속했을 때 값 copy_big(N_1,N); decrese(N_1); s=0; a = N_1 + 1; mask = 0x01; exitFlag = -1; while((a <= (N_1 + SIZE(N_1))) && (exitFlag == -1)){ mask = 0x01; for(i=0;i<(sizeof(INT)*8);i++){ if( (*a & mask) != 0){ exitFlag = 1; break; } mask <<= 1; s++; } } //D: n-1을 2^s로 나눈값 = s만큼 오른쪽 쉬프트한 값 copy_big(D,N_1); shiftright(D,s); //k회만큼 테스트 exitFlag = -1; for(i=0;i<k;i++){ exitFlag = -1; while(exitFlag == -1){ bitsNum = 0; while(bitsNum < 2){ bitsNum = (int)(next_random_float() * n_bitsLen); } //N보다 작은 A생성. bitsNum이 n_bitsLen과 같은 경우 N보다 큰 난수 발생가능성 있음 generate_random(A,bitsNum); if((A[0] == 0) || (A[0]==1 && A[1]==1)){ continue; }else if(compare_big(A,N) == -1){ exitFlag = 1; break; } } //생성된 난수 A와 N사이에 최대공약수가 있는지 확인. //이 확인방법은 Rabin-Miller 방법에는 없지만 삽입함 //그럼으로써, gcd판별이라는 적은 공수를 들이고, strong liar한 N을 좀더 빨리 찾아낼 수 있음 gcd(A,N,Z); if(!((Z[0]==1) && (Z[1]==1))){ return not_prime; } //z = A^D mod n copy_big(Z,A); mod_exp(Z,D,N,R); //z == 1 or z==n-1 result = -1; if(((Z[0]==1) && (Z[1]==1)) || (compare_big(Z,N_1)==0)){ result = 1; } //s-1회까지 z^2 mod n == (n-1) 인지 확인 for(j=0; (result == -1) && (j<s);j++){ mod_square(Z,N,Z); //1이면 composit if((Z[0]==1) && (Z[1]==1)){ return not_prime; }else if(compare_big(Z,N_1) == 0){ result = 1; break; } } if(result == -1) return not_prime; } return prime; }
파일들
014.rabin_miller.zip
'암호화프로그래밍 > (Old)C-BIGINT' 카테고리의 다른 글
| 022. 활용 (0) | 2013.10.17 |
|---|---|
| 020. 난수(Random Number) (0) | 2013.09.11 |
| 019. 기수변환 (0) | 2013.09.03 |
| 018. 거듭제곱 (0) | 2013.08.26 |
| 017. 비트 수 세기 (0) | 2013.08.22 |