빠른 거듭제곱 알고리즘(Fast Exponentiation Algorithm)

아래 수식을 계산하는 함수를 구현하면 가장 간단한 방법으로 a를 n-1번 곱하는 방법이 있을 것 같다.

$a^{n}$

이때 n이 1023이라면 a를 1022번 곱해야 한다.

하지만 빠른 거듭제곱 알고리즘(fast exponentiation algorithm)을 사용하면 최소 10번 최대 20번의 계산으로 결과를 낼 수 있다.

빠른 거듭제곱 알고리즘은 Square and Multiply 개념을 이용한 알고리즘이다.

Square and Multiply 개념은 아래 수식으로 간단하게 설명할 수 있다.

$a^{9} = a^{1001_{2}} = a^{8} * 1 * 1 * a$

빠른 거듭제곱 알고리즘(Fast Exponentiation Algorithm)

빠른 거듭제곱 알고리즘은 아래와 같은 프로세스를 가진다.

1. 지수를 2진수로 변환했을 때 LSB가 1인지 확인한다.

2. 만약 0이라면? => 제곱만 한다. (Square)
   만약 1이라면? => 제곱하고 곱한다. (Square and Multiply)

3. 다음 bit를 확인하기 위해 지수를 2진수로 변환했을 때 기준 right shift 한다.

아래는 모듈러 연산에서의 빠른 거듭제곱 알고리즘을 python으로 구현한 코드이다.

def fastExponentiation(a, x, n):    # a^x mod n
    y = 1
    while x > 0:
        if x & 1  == 1:         # 지수의 LSB가 1인지 확인
            y = (a * y) % n     # Multiply Operation
        a = (a * a) % n         # Square Operation
        x = x >> 1
    return y