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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 2334 天前的主题，其中的信息可能已经有所发展或是发生改变。

7x + 120y = 1

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

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

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

120 = 7*17 +1

嘿嘿，求帮助

8 条回复 • 2018-08-04 22:29:08 +08:00

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 via Android

－ 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 via Android

https://www.cs.drexel.edu/~jpopyack/IntroCS/HW/RSAWorksheet.html
前段时间复习密码学重新学了 RSA
楼主能不能好好看书再提问…港真，要快多了。楼上也都说了，负数要再取模。

channg

2018-08-04 22:29:08 +08:00

@zjp 看到了生产环境应为都使用超大数不会产生这样的结果