2 baidu 25110797 baidu_25110797 于 2015.07.09 16:01 提问

可以来给我看看程序么,有些不太懂

UpdateData(TRUE);
int x[4],y[4],t[4],q,i;
x[1]=1;
x[2]=0;
y[1]=0;
y[2]=1;
x[3]=m_Qn;
y[3]=m_e;

while(y[3]!=1)
{

if(y[3]==0)
{
AfxMessageBox("密钥不存在");
break;
}

q=x[3]/y[3];//算法的核心

for(i=1;i<4;i++)
{
t[i]=x[i]-q*y[i];
x[i]=y[i];
y[i]=t[i];
}//算法的核心
}
if(y[3]==1)
{//判断退出while的原因
if(y[2]<0) //这个判断语句是我自己添的,使m_d为大于零的数且不影响要求的。
{
y[2]=m_Qn+y[2];
}
m_d=y[2];
}
UpdateData(FALSE);

中间的循环看不懂,是怎样利用欧几里得算法的啊??????

3个回答

bdmh
bdmh   Ds   Rxr 2015.07.09 16:05

中间for循环就是交换x和y的值,关键就是q值,q为什么这样计算,这个应是你要去弄明白的

bdmh
bdmh   Ds   Rxr 2015.07.09 16:06

算法网上都有解释,你最好先搞明白什么事欧几里得,然后再看代码

frank_20080215
frank_20080215   2015.07.09 17:01

定理:gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不为0)
证明:a可以表示成a = kb + r,则r = a mod b
假设d是a,b的一个公约数,则有
d|a,d|b,而r = a - kb,因此d|r
因此d也是(b,a mod b)的公约数
因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证
或:证明:
第一步:令c=gcd(a,b),则设a=mc,b=nc
第二步:根据前提可知r =a-kb=mc-knc=(m-kn)c
第三步:根据第二步结果可知c也是r的因数
第四步:可以断定m-kn与n互素【否则,可设m-kn=xd,n=yd,(d>1),则m=kn+xd=kyd+xd=(ky+x)d,则a=mc=(ky+x)dc,b=nc=ycd,故a与b最大公约数≥cd,而非c,与前面结论矛盾】
从而可知gcd(b,r)=c,继而gcd(a,b)=gcd(b,r),得证

Csdn user default icon
上传中...
上传图片
插入图片