고속 누승 알고리즘과 모듈러 연산
누승 알고리즘이란 거듭 제곱을 의미하고 모듈러 연산이란 % 연산자이다.
거듭 제곱은 while 문으로 계속 a를 곱하면 되고
모듈러는 % 연산자로 해결 하면 되니 바로 코드를 짜보자.
int expo_algorism(int a, int b, int n) { int result = 1; while( b > 0 ) { result = (result * a) % n ; b--; } return result; }
a ^ b mod n 의 값을 계산 해주는 코드가 바로 완성 됬다.
하지만 여기서 문제가 하나 있다. 암호 수학 에서 쓰는 수는 매우 큰 숫자를 사용한다.
그렇기에 a ^ b 에서 b=1000이 넘어가 버리면 약 10^300 년 정도 걸리기에 실 사용이 불가능하다.
그렇기에 위와 같은 문제점을 해결한 알고리즘을 짜보도록 하자.
a ^ 30 = (a ^ 15) ^2 : 제곱셈 1회
a ^ 15 = (a ^ 7 )^2 * a : 제곱셈 1회 + 곱셈 1회
a ^ 7 = (a ^3 ) ^ 2 * a : 제곱셈 1회 + 곱셈 1회
a ^ 3 = (a ^ 2 ) ^ a : 제곱셈 1회 + 곱셈 1회
총 : 제곱셈 4회 + 곱셈 3회 = 7회
이렇게 계산 한다면 계산 횟수가 확실히 적어지게 된다.
그럼 위의 알고리즘을 이용하여 코드를 만들어 보도록 하자.
INT expo_algorism(INT a, INT b, INT n) { INT result = 1; while(b) { if(b & 1) { result = (result * a) % n ; } b /= 2; a = (a * a) % n ; } return result; }
이 코드도 a ^ b mod n 을 계산해 주는 프로그램이지만 개선된 알고리즘을 사용해 더 빠른 속도로 연산을 해낼 수 있게 되었다.
간단히 분석해보자면
1.
if(b & 1) { result = (result * a) % n ; }
이 부분은 b&1(=b가 홀수) 일 때 × a를 하고 mod n 값을 구한다.
2.
b /= 2; a = (a * a) % n ;
지수 (b)를 절반씩 줄이고 a에 a^2을 한 뒤 mod n 의 값을 넣는다.
이것으로 RSA를 만들기 위한 준비는 끝이 났다.
다음 글에선 부가적인 설명 없이 바로 RSA를 만들도록 하겠다.