계수는 전원

Question

의 나는 a^b mod m의 계산으로, b > 2^63 - 1 그래서 우리는 모듈 식 지수 코드를 수정할 수 모듈러 지수하지만 난 데 문제가 내가 가지고있는 b는 매우 큰 가치가 있다는 것입니다을 사용 가능하다는 문제가 있었다

 
function modular_pow(base, exponent, modulus) 
    result := 1 
    while exponent > 0 
     if (exponent mod 2 == 1): 
      result := (result * base) mod modulus 
     exponent := exponent >> 1 
     base = (base * base) mod modulus 
    return result 

는 큰 b

수용하기 위해 또는 그 a^b mod m(a^(b mod m)) mod m가 같다고 맞습니까?

Answer 1

그것은 맞습니다 또한 두 가지 방법

을 결합 할 수

(유형 모든 값을 표현하기에 충분히 긴 경우) 파이가 (m)은 귀하의 코드가 너무 정확 Euler totient function

입니다 a^b mod m = a^(b mod phi(m)) mod m, 그