[제 6강] 고속 누승 알고리즘과 모듈러

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

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

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

글의 문제가 있다면 댓글을 달아 주세요.

This site uses Akismet to reduce spam. Learn how your comment data is processed.