이 알고리즘을 해석할 때 헷갈리게 하는 요소는 바로 x 라고 생각되네요.
x 에 대한 이해를 하기 전에 mod의 특성에 대해서 먼저 알아야 합니다.
쓰다보니 좀 복잡하게 써지네요. 쉽게 써보려 했습니다만....
--
어떤 두 숫자 a, b 가 있고, mod를 하는 숫자 m 이 있다고 할 때
(a * b) mod m = ( (a mod m) * (b mod m) ) mod m 이 성립합니다.
이게 무슨 뜻이냐하면요,
두 숫자의 곱을 m 으로 나눈 나머지는 두 숫자를 m 으로 나눈 나머지를 서로 곱한 것을 다시 m 으로 나눈 나머지와 같다는 뜻입니다.
이것의 증명은 매우 쉽습니다. a = c * m + d, b = e * m + f 라고 하면 (곧 a mod m = d 이고 b mod m = f 인 셈입니다만)
a * b = (c * m + d) * (e * m + f ) = c*e*m*m + (c*f + d*e)*m + d*f
이러면 a * b mod m 을 하게 되면 c*e*m*m은 m으로 나누어 떨어지고 (c*f + d*e)*m도 m으로 나누어 떨어지므로 남은 d*f mod m 과 같은데 d는 a mod m 이었고, f는 b mod m 이었으니 증명된 셈입니다.
이걸 이해하는게 중요한 이유는 3^644 mod 645를 구하는데 있어서 3^644를 여러 숫자로 분리해서 곱셈으로 재정의하면 각 분리된 숫자들의 mod 645 값을 구해서 곱하는 것으로 값을 구할 수 있다는 점입니다.
3^644 mod 645를 구하는 방법은 644를 2진수로 바꿔보는 겁니다.
644는 문제에 나온 대로 1010000100 입니다. 이걸 해석하면 644 = 2^9 + 2^7 + 2^2 로 해석이 됩니다.
3^644는 3의 644번 제곱이므로 3^(2^9) * 3^(2^7) * 3^(2^2) 으로 펼쳐서 표현할 수 있겠습니다.
위의 알고리즘이 하는 것은 3^1 부터 그것의 제곱 3^2, 그 다음 그것의 제곱(3^2^2), 그 다음 그것의 제곱(3^2^2^2 = 3^2^3), 그 다음 그것의 제곱(3^2^3^2 = 3^2^4)... 이렇게 계속 제곱을 해서 해당 값의 mod 645를 구하고 있습니다. 그리고 2진수 상으로 해당 위치의 값이 1인 자리에 대해서 그 자리의 나머지를 계속 곱해주면 되는 것이지요.
power0 = 3 = 3^(2^0)
power1 = 3*3 = 3^(2^1)
power2 = 3^(2^2)
power3 = 3^(2^3)
power4 = 3^(2^4)
사실 power0는 3, power1은 그것의 제곱이 9, power2는 그것의 제곱인 81, power3는 그것의 제곱인 6561... 이런 값이 나오게 되는데, 각 지점마다 mod 645를 해서 나머지를 구해두는 작업을 하는 것이고요,
최종적으로는 644 = 2^9 + 2^7 + 2^2 이었으므로 power9, power7, power2 값을 구해서 power9 * power7 * power2 mod 645를 구해주기만 하면 되는 것이긴 했습니다.
위의 알고리즘에서 x가 헷갈릴 수 있다는 얘길 한 것은 계속 제곱을 해서 power0부터 1, 2, 3... 값을 찾아두는 과정에서 해당 자리가 2진수 변환시 644에서 1인 자리라면 해당 자리는 곱셈에 포함해야 하므로, 이 곱셈되는 시점에 바로바로 계산을 해준다는 차이점이 있었을 뿐입니다. 결과적으로는 앞에서 얘기한 것 처럼 power9 * power7 * power2 mod 645를 구하면 답이 되는 것이지요.
위의 알고리즘이 fast로 표현될 수 있는 이유는 3^k 라고 할 때 k가 어떤 숫자이든 2진수로 변환할 수 있으며, 2진수로 변환했을 때 나오는 맨 앞자리수까지만 power0, power1, power2... 이렇게 순차적으로 찾아가면 이 power 수열을 구할 수 있으며... 3의 제곱에 제곱에 제곱에... 이런 큰 수에 대한 계산을 매번 이미 645로 나누어주면서 숫자가 무한히 커지는 것을 방지하고 있다는 점. 그리고, 위의 예제에서 볼 수 있지만 3을 계속 제곱제곱 하다보면 숫자가 어느 시점부터 순환하기 때문에 실질적으로는 주어진 제곱 수가 몇십만이 되더라도 아마 매우 빠르게 계산이 가능할 것이라는 점입니다.
(*) 앞에서 설명을 다 했지만 어떤 자리 power의 i 번째 자리 power_i 값을 구했다고 할 때,
power의 i+1번째 값을 구하는 방법은
( power_i * power_i ) mod m = ( (power_i mod m) * (power_i mod m) ) mod m 으로 구해집니다.
위의 그림에도 나오지만 power4를 구할 때는 power3를 제곱해서 mod 645를 해주고 있지요
