[求助]关于辗转相除法的问题??高手帮忙!!
已知e,n,两个都比较大.
(e*d) mod n=1
求用辗转相除法求出d???
大家帮帮忙啊,小弟感激不尽!
问题点数：0、回复次数：19Top
1 楼hai_li（何家干）回复于 2004-12-02 12:47:44 得分 0
这儿的d可定不是唯一的啊！哪还怎么求以具体的值啊！Top
2 楼pcboyxhy（-273.15℃）回复于 2004-12-02 12:53:38 得分 0
还用算？
d=1就行。
如果e mod n !=1,
d就是浮点数了Top
3 楼pomelowu（羽战士）回复于 2004-12-02 13:01:34 得分 0
用辗转相除，求e，n的最大公约数，如果不是1则d不存在。
但是如果是1，即e，n互质，可以用循环求。
如果这个找d的过程也要用辗转相除，暂时还没想出来。Top
4 楼DiabloWalkOnTheEarth（我想到个绝妙的昵称,只是地方太小,写不下）回复于 2004-12-02 13:04:41 得分 0
做 RSA 吗?下个加密库吧, openssl 或者 cryptlib 都不错.Top
5 楼tchain（）回复于 2004-12-02 15:18:25 得分 0
呵呵是啊,是rsa,高手果然是高手啊
是学校留的题,因为快考试了没有多少时间,我们不是计算机专业的.所以想请各位帮帮忙啊.
求出最小的一个d就可以了,用循环计算的话计算量太大了,e和n都是比较大的数,起码得几万.各位帮忙想一个比较简单我能看的懂的就行了,谢谢了!!!Top
6 楼DiabloWalkOnTheEarth（我想到个绝妙的昵称,只是地方太小,写不下）回复于 2004-12-02 15:50:45 得分 0
e , n 不是几万,最少得 2^512 , 看你得情况还是用 cryptlib 吧, 要了解原理就看看<<计算机密码学>> , 看了就可以理解了, 看代码就看看 CryptoPP::EuclideanMultiplicativeInverse , 写的满清晰的. 如果是应用的话, cryptlib 的接口定义的满好的,咔咔.Top
7 楼tchain（）回复于 2004-12-02 16:26:22 得分 0
晕~~~~我只用循环法做出几百来,因为再大用普通算法就很容易数据溢出了!!!
偶不是计算机专业的,因为被逼无奈必须得交这个作业,我只要实现用辗转相除法处理一下个位数的加密就可以了.唉数学有点差,觉得很难把辗转相除法和求这个联系起来!别人给了一个算法是vb的可是完全看不懂!!
高手帮我写一个看一下啊!Top
8 楼tchain（）回复于 2004-12-02 20:53:42 得分 0
各位帮帮忙啊!!!!Top
9 楼tchain（）回复于 2004-12-03 09:03:00 得分 0
没有人顶吗?
我的水平实在有点看不懂那么深的东西啊!各位帮忙啊,帮我写一个!!Top
10 楼xiaoxiaofei（小小飞）回复于 2004-12-03 10:38:57 得分 0
我日!我有辗转相除法的步骤,可是发不上来,系统提示:请不要发对我们有害的言论!!!!!!!!!!!Top
11 楼scu_hurricane（金文丰）回复于 2004-12-03 20:47:21 得分 0
首先要做大数运算的程序，就是用数组来存放大数，然后再用辗转相除法。Top
12 楼xiaoxiaofei（小小飞）回复于 2004-12-06 17:12:26 得分 0
欧几里德求m,n最大公约数算法:
1'如果n=0,返回m作为结果,结束;否则进入下一步.
2'用n去除m,余数赋给r.
3'n值赋给m,r值赋给n,返回第一步.Top
13 楼xiaoxiaofei（小小飞）回复于 2004-12-06 17:15:24 得分 0
这种方法通常称为辗转相除法,脱胎于两个多项式的最大公因式算法(主要是算法思想,参看<高等代数>高等教育出版社,多项式章'最大公因式节)Top
14 楼cugwei（伟~~~盈）回复于 2004-12-06 17:45:31 得分 0
可以的
用回溯写Top
15 楼cugwei（伟~~~盈）回复于 2004-12-06 17:47:49 得分 0
int euclid(int a,int b,int s,int t,int ss,int tt){
if(b==0) return s;
return euclid(b,a%b,s,t,s-ss*(a/b),tempt=t-tt*(a/b));
}
Top
16 楼cugwei（伟~~~盈）回复于 2004-12-06 17:51:43 得分 0
开始时 s=1,t=0,ss=0,tt=1
返回的s就是(a,b)=(s)*a+(t)*b
Top
17 楼ahhy（蓝色海洋）回复于 2004-12-06 18:10:16 得分 0
欧几里德求m,n最大公约数算法:
1'如果n=0,返回m作为结果,结束;否则进入下一步.
2'用n去除m,余数赋给r.
3'n值赋给m,r值赋给n,返回第一步.
up
其实就是这个循环呀Top
18 楼cugwei（伟~~~盈）回复于 2004-12-06 18:19:57 得分 0
呵呵
我是直接返回乘法逆(ａ^-1) 即（a^-1）×a ≡1( mod b )Top
19 楼cugwei（伟~~~盈）回复于 2004-12-06 18:32:41 得分 0
上面的错了
int euclid(int a,int b,int s,int t,int ss,int tt){
if(b==0) return s;
return euclid(b,a%b,s,t,s-ss*(a/b),t-tt*(a/b));
}
另 返回的可能是负数 只要将返回值加上 b 就可以了
Top
