指数求模

2019-04-13 12:44发布

站内文章 / 模拟电子
17229 0 1647

指数幂求模

comupte aj mod pcomupte a^{j} mod p

Formular

(pq) mod N = ((p mod N)*(q mod N)) mod N at={a(aj/2)2j is odd number(aj/2)2j is even numbera^{t}=left{ egin{aligned} a(a^{j/2})^{2}& & j is odd number\ (a^{j/2})^{2} && j is even number end{aligned} ight.

Code Implementation

// // main.cpp // ModularExponent // // Created by Ronald on 2018/10/16. // Copyright © 2018 Ronald. All rights reserved. // #include #include using namespace std; //compute a^j%p int modular_exponent_re(int a,int j, int p){ if(p<0){ return -1; } if(j==0){ return 1; }else{ int z = modular_exponent_re(a, j/2, p); if(j%2==0){ return ((z%p)*(z%p))%p; }else{ return (a*(z%p)*(z%p))%p; } } } int modular_exponent(int a,int j,int p){ if(j<0){ return -1; } if(j==0){ return 1; }else{ stack<int> s; int result = a; while(j){ s.push(j); j=j/2; } while (s.size()>1) { int t = s.top(); s.pop(); result = ((result%p)*(result%p))%p; if (s.empty()) { break; } if (t*2 != s.top()) { result = ((a%p)*result)%p; } } return result; } } int modular_exponent1(int a,int j,int p){ if(j<0){ return -1; } if(j==0){ return 1; }else{ int result = 1; while (j>0) { if (j%2!=0) { result = (a*result)%p; } // result = ((result%p)*(result%p))%p; //a=(a*a)%p a = a%p; a=(a*a)%p; j=j/2; } return result; } } s=1
if j is odd s=s*a
(a2)j/2(a^{2})^{j/2} int modular_exponent_trick(int a,int j,int p){ int s = 1; while(j){ if (j%2 != 0) { s = (s*a)%p; } a = (a*a)%p; j=j/2; } return s; } int main(int argc, const char * argv[]) { // insert code here... std::cout << "Hello, World! "; std::cout << modular_exponent_re(3, 10, 31)<<endl; std::cout << modular_exponent(3, 10, 31)<<endl; std::cout << modular_exponent_trick(3, 10, 31)<<endl; return 0; }

热门文章