expmod 모듈러 지수화 알고리즘 친절한 설명

모듈러 지수화 알고리즘이란

모듈러 지수화 알고리즘이란,
어떤 수를 지수연산한 결과를 다른 수로 나누어 나머지를 구하는 알고리즘입니다.
지수연산이 다 끝나기 전에 연산하는 수의 크기를 크게 줄여줘서 메모리 친화적인 알고리즘입니다.

아래의 식이 모듈러 지수화 알고리즘의 핵심인 모듈러 곱셈입니다.

$ab\mod{m}=[(a\mod{m})(b\mod{m})]\mod{m}$
($a \mod b$)는 a를 b로 나눈 나머지를 뜻합니다.

놀랍지 않습니까?
($ab$의 나머지)를 구하려고 하는데,
이 값은 ($a$의 나머지)와 ($b$의 나머지)의 곱의 나머지와 같습니다.

모듈러 곱셈 증명

$ab\mod{m}=[(a\mod{m})(b\mod{m})]\mod{m}$을 증명하겠습니다.

$a=m\times q'+r'$
$b=m\times q''+r''$
($q'$와 $q''$는 몫, $r'$과 $r''$는 나머지)

$ab\mod{m}$
$=(m\times q'+r')(m\times q''+r'')\mod{m}$
$=(m^2q'q''+mq''r+mq'r''+r'r'')\mod{m}$

여기서 m을 인수로 포함한 항은 $\mod m$에 의해 지워집니다.

$ab\mod{m}$
$=r'r''\mod{m}$

$∴ ab\mod{m}=[(a\mod{m})(b\mod{m})]\mod{m}$

모듈러 곰셈을 이용한 expmod

$b^n\mod{m}$을 계산한다고 합시다.

$n=2k$라면, (짝수라면)

$b^{2k}\mod{m}$
$=[(b^k\mod{m})(b^k\mod{m})]\mod{m}$
$=(b^k\mod{m})^2\mod{m}$

$n=2k+1$이라면, (홀수라면)

$b^{2k+1}\mod{m}$
$=[(b\mod{m})(b^{2k}\mod{m})]\mod{m}$
$=b(b^{2k}\mod{m})\mod{m}$
($b=mq+r$로 놓고 계산해 보면 m이 포함된 부분을 결국 사라지므로, $(b\mod{m})$를 $b$로 대체 가능하다.)

위의 알고리즘을 사용한다면, 메모리를 초과하지 않고도 지수연산의 결과에 모듈러 연산을 할 수 있습니다.
구현된 프로시저를 스킴으로 나타내면 아래와 같습니다.

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

긴 글 읽어주셔서 감사합니다.