모듈러 지수화

Question

C/C++에서 (a^b)%m은 어떻게 계산합니까? b은 64 비트에 맞지 않습니다. 즉, b 대신 b%m을 사용하여 위의 값을 계산하는 방법이 있습니까?

그리고 O(log(b)) 시간 또는 O(log(b%m)) 시간에 위의 결과를 계산할 수있는 알고리즘이 있습니까? Euler's theorem에 따르면

Answer 1

, a 및 m가 서로 소 경우 :

가

ab mod m = ab mod phi(m) mod m

그렇게 b가 큰 경우, 당신은 b 대신 값 b % phi(m)을 사용할 수 있습니다. phi(m)은 Euler's totient function이며, 소수 분해가 m 인 경우 쉽게 계산할 수 있습니다.

이렇게 b의 값을 줄이면 Exponentiation by squaring을 사용하여 모듈러 지수를 O(log (b % phi(m)))으로 계산하십시오.