扩展欧几里得算法，求 7 对 120 的模逆元

2018-08-04 17:45:35 +08:00
 channg

7x + 120y = 1

为什么我跑程序算出来的都是 103

然后我手算的时候算的都是-17

我知道我算的不对 但是辗转相除好像没问题啊

120 = 7*17 +1

嘿嘿，求帮助

3090 次点击
所在节点    问与答
8 条回复
channg
2018-08-04 17:47:07 +08:00
7*103 + (-6)*12 = 1

7*(-17) + 120 * 1 = 1
yanaraika
2018-08-04 17:51:23 +08:00
逆元一般说的是 0~n-1 之内的那个
zmxnv123
2018-08-04 17:51:45 +08:00
－ 17 mod 120 =103
yanaraika
2018-08-04 17:51:50 +08:00
在模 120 意义上-17 和 103 是一样的
channg
2018-08-04 17:53:28 +08:00
@yanaraika 因为-17 算 rsa 算不对。。
channg
2018-08-04 18:23:39 +08:00
rsa 私钥好像不能用负数啊
zjp
2018-08-04 18:35:23 +08:00
https://www.cs.drexel.edu/~jpopyack/IntroCS/HW/RSAWorksheet.html
前段时间复习密码学重新学了 RSA
楼主能不能好好看书再提问…港真，要快多了。楼上也都说了，负数要再取模。
channg
2018-08-04 22:29:08 +08:00
@zjp 看到了 生产环境应为都使用超大数不会产生这样的结果

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/476884

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX