[Java] 모듈러 제곱근

모듈러 제곱근이란?

거듭제곱근(P^N)을 효과적으로 계산하기 위한 방식

 

 

거듭제곱근을 구하기 위해서 단순 루프를 돌면서 곱셈을 하였을 때, 그 횟수가 늘어날수록 극격히 비효율적이 된다.

 

단순 루프

for(int i = 0; i < N; i ++) {
	P *= P;
}

위와 같은 방식으로 P^N을 구하면 O(N)의 시간복잡도를 갖는다.

 

모듈러 제곱근 예시 코드

public static long power(long P, long N) {
    long result = 1;

    while(N > 0) {
        if(N % 2 == 1) {
            result *= P;
        }
        P *= P;
        N /= 2;
    }

    return result;
}

모듈러 제곱근을 이용하면 O(logN)의 시간 복잡도로 계산할 수 있다.

 

위 코드는 2진수의 쉬프트 연산과 같은 동작이라고 이해할 수 있다.