模取幂运算a^b mod n的问题
小弟初学，下面是我在网上看到的一个模取幂的程序，有几个地方看不懂，请高手指点一下。
/**//****************************************************/
// 模取幂运算 计算a^b mod c
// 利用公式
// (a*b)mod(c) = ((a mod c )*b)mod c
/**//****************************************************/
int a_b_Mod_c(int a, int b, int c)
{//前提 a b c 都是正数
int digit[32]; //最好讲解一下为什么要把b转成2进制？？？这样有什么好处
int i, k, resualt = 1; //这里的reuslt存放什么数据的，为什么初始化值为1？？？？？？？？？？
i = 0;
while(b)//把b化成2进制
{
digit[i ] = b%2;
b >>= 1;
}
//计算(a^b) mod c
for(k = i-1; k >= 0; k--)
{
resualt = (resualt * resualt) % c; //这句看不懂？？？？？？？？？？？？
if(digit[k] == 1)
{
resualt = (resualt * a) % c; //这句也看不懂？？？？？？？？？？？
}
}
return resualt;
}
网友回复:http://blog.csdn.net/dremi/archive/2007/04/17/1568221.aspx,这里有解答
网友回复:这个是把转换为3进制的
- C/C code
Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ int a_b_Mod_c(int a, int b, int c) {//前提 a b c 都是正数 int digit[32]; int i, k, resualt = 1; i = 0; while(b)//把b化成3进制 { digit[i ] = b%3; b /=3 ; } //计算(a^b) mod c for(k = i-1; k >= 0; k--) { resualt = (resualt * resualt * resualt) % c; //因为基数是3，所以要3个resualt相乘意 if(digit[k] == 1) { resualt = (resualt * a) % c; //因为3进制会出现0，1，2，当为1时就乘一个a } else if(digit[k]==2) { resualt = (resualt *a*a) % c;//当为2时乘两个a } } return resualt; }
四进制的
- C/C code
Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ int a_b_Mod_c(int a, int b, int c) {//前提 a b c 都是正数 int digit[32]; int i, k, resualt = 1; i = 0; while(b)//把b化成4进制 { digit[i ] = b%4; b /=4; } //计算(a^b) mod c for(k = i-1; k >= 0; k--) { resualt = (resualt * resualt*resualt*resualt) % c; //基数是4，4个resualt if(digit[k] == 1) { resualt = (resualt * a) % c; //会出现0，1，2，3 如上 } if(digit[k]==2) resualt = (resualt * a *a) % c; //为2时 如上 if(digit[k]==3) resualt = (resualt * a * a * a) % c; //为3时 如上 } return resualt; }
转换为2进制的就很好理解了，其实和10进制一样的道理，也许把b转换为2进制效率要高点吧
网友回复:
- C/C code
Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ / (((a^(b/2))%mod)^2)%mod b%2=0 (a^b)%mod=| \ (((a^(b/2))%mod)^2*a)%mod b%2=1
根据上面的式子,可以直接用递归,也就是从顶向下来计算,或者我们自底而上来计算.
从上面的式子中我们注重到,我们是按b%2的情况来递归地计算a^b%mod的,于是,在整个递归过程中,我们是按b的二进制展开形式来计算的,假如我们实现得到了b的二进制形式,我们就可以自底而上的计算a^b%mod了.
resualt存放的自然是a^b%mod的结果,至于为什么初始化为1,很简单,就不讲了.
你看不懂的哪两句就是公式中的两个分支了.
网友回复:
- C/C code
Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ /**//****************************************************/ // 模取幂运算 计算a^b mod c // 利用公式 // (a*b)mod(c) = ((a mod c )*b)mod c /**//****************************************************/ int a_b_Mod_c(int a, int b, int c) {//前提 a b c 都是正数 int digit[32]; //最好讲解一下为什么要把b转成2进制？？？这样有什么好处 int i, k, resualt = 1; //这里的reuslt存放什么数据的，为什么初始化值为1？？？？？？？？？？ i = 0; while(b)//把b化成2进制 { digit[i ] = b%2; b >>= 1; } //计算(a^b) mod c for(k = i-1; k >= 0; k--) { resualt = (resualt * resualt) % c; //这句看不懂？？？？？？？？？？？？ if(digit[k] == 1) { resualt = (resualt * a) % c; //这句也看不懂？？？？？？？？？？？ } } return resualt; }
帮你整理一下
网友回复:
- C/C code
Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ /*递归解法*/ #include <iostream> using namespace std; int RSA(int a,int b,int n) { if(b==0) return 1; if(b%2==0) return RSA(a,b/2,n)*RSA(a,b/2,n)%n; else return RSA(a,b/2,n)*RSA(a,b/2,n)*a%n; } int main() { int a,b,n; cin>>a>>b>>n; cout<<RSA(a,b,n)<<endl; return 0; }
文章评论
共有 0 位网友发表了评论 此处只显示部分留言 点击查看完整评论页面