rsa中求密钥的euclidean算法（纯数学）书上看到rsa算法计算密钥时，求3533^-1mod11200,按照常理3mod5=3肯定不对，书上给的答案是6597（3533*6597-1再除11200确实是整数），提示用euclidean算法，但没说

Question

rsa中求密钥的euclidean算法（纯数学）
书上看到rsa算法计算密钥时，求3533^-1 mod 11200,按照常理3mod5=3肯定不对，书上给的答案是6597（3533*6597-1再除11200确实是整数），提示用euclidean算法，但没说明。网上查到一个：
求357^－1 mod 1234
1234=3*357+163
357=2*163+31
163=5*31+8
31=3*8+7
8=1*7+1
则
1=8-(1*7)
=8-(31-3*8)
=4*8-31
=4*(163-5*31)-31
=4*163-21*31
=4*163-21*(357-2*163)
=46*163-21*357
=46*(1234-3*357)-21*357
=-149*357+46*1234
357^－1 mod 1234=-149
这个本不是求gcd的吗，怎么用在这了？
我自己套了一遍，最后结果和答案不同，但是验算正确）
11200=3533*3+601
3533=601*5+528
...
5=2*2+1
然后逐行向上
1=5-2*2
=5-2*(17-5*3)
...
=1452*11200-4603*3533
我这个3533前边是-4603，-4603*3533-1也可以被11200整除
请问正确的步骤是怎样的，一个公钥算出两个密钥肯定不对吧

Answer 1

哥们，这两个答案是一样的，因为
-4603=6597（mod11200）
因为4603+6597=11200，习惯上我们取正同余数，所以就是6597。算法就是辗转相除，没问题。