C++의 모듈러 지수화

Question

모듈러 지수법에 대한 내 코드에 문제가있어 두 가지 다른 의사 코드 소스를 사용할 때 세 번 쓰지 만 문제를 발견 할 수 없습니다. SE의 C++에서 모듈러 지수법에 대한 다른 질문을 읽었지 만 그 점이 도움이되지 못했습니다. 다음은 내가 생각하는 간단하지만 적은 최적의 방법에 의해 쓰여진 마지막 코드입니다 :

#include<iostream> 
using namespace std; 

// base^exponent mod modulus 
unsigned mulmod1(unsigned base, unsigned exponent, unsigned modulus) { 
    int result = 1; 
    while(exponent > 0){ 
     if(exponent % 2 == 1) 
      result = (result * base) % modulus; 
     exponent >>= 1; 
     base = (base * base) % modulus; 
    } 
    return result; 
} 

int main(){ 

//9688563^45896 mod 71 = 30 
//12^53 mod 7 = 3 

cout<<mulmod1(9688563,45896 ,71)<<"\n"; //gives 10 instead of 30 
cout<<mulmod1(12,53,7)<<"\n";    //gives correct answer 3 

return 0; 
} 

Answer 1

이 함수 mulmod1에 대한 입력을 소독합니다! unsigned은 9688563*9688563을 보유 할 수 없습니다. 이 작업을 제대로 수행하려면 모듈화 된 지수 연산을 올바르게 수행하기 위해 modulus * modulus (물론 입력 번호)을 저장할 수있는 데이터 형식 만 있으면됩니다.