모듈러 곰셈을 이용한 거듭제곱의 나머지 연산

모듈러 곱셈이라는 것을 처음알게 되었다. 잊지 않도록 기록해 놓는다.

출처 : 칸 아카데미

모듈러 연산의 곱셈 성질
(A * B) % C = (A % C) * (B % C) % C

예제
4의 8승을 7로 나누었을 때의 나머지는?
(4 ** 4) ** 2 = 256 * 256 => {(256 % 7) * (256 % 7) % 7} = (4 * 4 % 7) = (4 ** 8 % 7) = 2

좀더 자세한 내용은 칸 아카데미에서 볼 수 있다.

문제 : 위의 법칙을 이용해서 4 ** 123456789123456789123456789123456789123456789 를 100000000000710000000000071000000000007 로 나눈 나머지를 구하시오.

해답

const calculate = (m, n, k) => {
    if(n === 0) return 1;
 
    const temp = calculate(m, Math.floor(n/2), k);
    return (n % 2 === 0) ? temp * temp % k : temp * temp * m % k;
};
 
calculate(4, 123456789123456789123456789123456789123456789, 100000000000710000000000071000000000007);