1629 곱셈
나머지 지수승 관련한 이산수학 교재 캡처 추가. 이 알고리즘이 기반한 원리는 \(b^4 \mod m\) 이나 \((b^2 \mod m) \cdot (b^2 \mod m) \mod m\) 이나 같다는 것이다. 주목할 변수는 x일지 몰라도 그 x에 붙일 계수를 알기 위해선 당연하게도 power를 지수승만큼 증가시켜야 한다. 그런데 그냥 \(b^1\) \(b^2\) \(b^3\) ... 이런식이 아닌, \(b^{2^1}\) \(b^{2^2}\) \(b^{2^3}\) 이런 식으로 증가하기 때문에 power를 매 이터레이션마다 제곱을 시키는 것이다.
아래 교재의 예시인 \(3^{644} \mod 645\)를 예로 들면, \(644 = 2^2 + 2^7 + 2^9\) 이므로, \(3^644 \mod 645 = 3^{2^{2}} \cdot 3^{2^{7}} \cdot 3^{2^{9}} \mod 645\)와 같다. 그래서 x는 i 가 2, 7, 9일때 x = (x * power) mod m을 구하고, power는 매 이터레이션마다 \(3^{2^{i}}\) 를 구하고 있는거고.
source code#
"""modular exponentiation 참고: https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-exponentiation"""
from math import ceil, log2
def modular_exponentiation(b: int, exp: int, m: int):
"""나머지 지수승 연산을 수행하는 알고리즘.
$$
b^{exp} \mod m
$$
"""
x = 1
power = b % m
k = ceil(log2(exp)) + 1 # e의 이진전개의 길이, 1을 더하는 이유는 예외처리 때문이다. 2의 지수승을 e에 넣어보고 풀면 결과가 이상하다. 왜냐하면 아래 for문의 if문을 하나도 통과하지 않기 때문이지.
for i in range(k):
if (exp >> i) & 1 == 1:
# a_i = 1 then,
x = (x * power) % m
power = (power * power) % m
return x
b, exp, m = [int(x) for x in input().split()]
print(modular_exponentiation(b, exp, m))