C/C++实现大数模指数运算-二进制算法（a^e mod m 当e特别巨大时...）

2019-04-13 13:00发布

站内文章 / 模拟电子
13957 0 1035
data/attach/1904/7ycz5be6o86i9ddhmx2rebvkrowqksc5.jpgdata/attach/1904/z60h5jq7hgfm1amd6r45s2ndgs77lalw.jpg 模指数运算: 已知a, e, m, 计算a^e mod m ➡ a: 底数, e: 指数, m: 模数  解决已知a, e, m, 计算a^e mod m 指数过大运算结果超出固定分配空间能够存储的最大值的问题。 可应用于公钥密码体制, 哈希函数等密码学问题中。 示例: 计算2^90 mod 13 
当e很大时, a^e溢出: 运算结果超出固定分配空间能够存储的最大值
solution:


代码实现： #include #include #include using namespace std; int main() { int base, exponent, modulo; cin >> base >> exponent >> modulo; int a = base;//底数 int e = exponent;//指数 int m = modulo;//模数 long long int s = 1, ti[1000] = {}, ai[1000] = { 0 }, at[1000] = {}; string Binary_e; while (e != 0)//用于把指数e转换为二进制Binary_e { Binary_e = (char)(e % 2 + '0') + Binary_e; e >>= 1; //val_/=2; } int sz = Binary_e.size();//字符串长度sz for (int i = 0; i < sz; i++) { ti[i] = Binary_e[i] - '0';//把二进制字符串Binary_e存入整型数组ti[]中 } cout << endl; at[0] = a; for (int i = 0; i
VS2015编译环境下：

热门文章