고속 누승 알고리즘과 모듈러 연산

누승 알고리즘이란 거듭 제곱을 의미하고 모듈러 연산이란 % 연산자이다.

거듭 제곱은 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를 만들도록 하겠다.