高难问题求解
1764434的1839次方对356295求模=？
求诸如这样的计算求解的快速算法
即高次平方求模的快速算法
用于公开密匙加密及解密中
问题点数：100、回复次数：8Top
1 楼mathe（）回复于 2002-04-17 07:36:10 得分 30
int value=1;
int mul=1764434;
int index=1839;
int mod=356295;
while(index)
{
if(index&1){
value*=mul;
value%=mod;
}
mul*=mul;
mul%=mod;
index>>=1;
}
return value;Top
2 楼IT_worker（IT工人）回复于 2002-04-17 09:04:38 得分 0
高手就是高手！upTop
3 楼bjay（ben）回复于 2002-04-17 09:30:37 得分 10
提点改进意见：
1、在while语句前应加入mul %=mod;。
2、由于mod =356295及2＾64 > 356295^2 > 2^32使得上面程序在32位机上已无法运算。建议使用64位机:-)。如果没有64位机，只好用前面有人讨论过的“大数存储问题”的解决方法了。
Top
4 楼cosmicrays（省港澳长途牌王）回复于 2002-04-17 14:20:37 得分 0
mathe() 兄，算法很好
bjay(ben) 兄，请教“大数存储问题”的解决方法Top
5 楼mathe（）回复于 2002-04-17 15:02:38 得分 0
有道理，其实上面的code只是一个Demo
Top
6 楼starfish（海星）回复于 2002-04-17 15:15:03 得分 60
下面这个算法求解模取幂更快一点：
Modular-Exponentiation(a, b, n) // 求 a^b mod n
1. c <- 0;
2. d <- 1;
3. 设<b[k],b[k-1],..b[0]>是b的二进制表示;
4. for i <- k downto 0
5. do c <- 2c;
6. d <- (d*d) mod n
7. if b[i] = 1
8. then c <- c＋１；
9. d <- (d*a) mod n;
10.return d;
算法中的变量ｃ其实可以省略，引入ｃ只是为了让算法更容易理解。当ｃ成倍增加时算法保持条件d = a^c mod n不变，直至c=b。如果输入a,b,n都是k位的数，则算法总共需要执行的算术运算次数为O(k)，总共需要执行的位操作为O(k^2)。
下面是该算法的C代码，其中的BitLength可以用log函数代替。
/*********************************************
返回x的二进制长度
*********************************************/
int BitLength(int x)
{
int d = 0;
while (x > 0) {
x >>= 1;
d++;
}
return d;
}
/*********************************************
返回x的二进制表示中从低到高的第i位
，最低位为第一位
*********************************************/
int BitAt(int x, int i)
{
return ( x & (1 << (i-1)) );
}
/*********************************************
模取幂运算 计算a^b mod n
*********************************************/
int Modular_Expoent(int a,int b,int n)
{
int i, y=1;
for (i = BitLength(b); i > 0; i--)
{
y = (y*y)%n;
if (BitAt(b,i) > 0)
y = (y*a)%n;
}
return y;
}Top
7 楼starfish（海星）回复于 2002-04-17 15:47:00 得分 0
#include <iostream>
using namespace std;
/*********************************************
返回x的二进制长度
*********************************************/
template <class T>
T BitLength(T x)
{
T d = 0;
while (x > 0) {
x >>= 1;
d++;
}
return d;
}
/*********************************************
返回x的二进制表示中从低到高的第i位
，最低位为第一位
*********************************************/
template <class T>
T BitAt(T x, T i)
{
return ( x & (1 << (i-1)) );
}
/*********************************************
模取幂运算 计算a^b mod n
*********************************************/
template <class T>
T Modular_Expoent(T a, T b, T n)
{
T i, y=1;
for (i = BitLength(b); i > 0; i--)
{
y = (y * y) % n;
if (BitAt(b,i) > 0)
y = (y * a) % n;
}
return y;
}
void main()
{
__int64 a, b, n;
//cin >> a >> b >> n;
a = 1764434;
b = 1839;
n = 356295;
cout << Modular_Expoent(a, b, n) << endl;
getchar();
getchar();
}
计算结果是138554Top
8 楼cosmicrays（省港澳长途牌王）回复于 2002-04-17 17:22:32 得分 0
谢谢诸位高手
mathe() 兄 30分
bjay(ben) 兄 10分
starfish(海星) 兄 60分
Top
