求大整数模逆算法 ！

B9-408

求大整数模逆算法 ！我查了相关资料说欧几里得算法的扩展！但是具体我研究了很久都一头雾水！希望那个高手给个求大整数模逆算法 参考参考！谢谢啊

knate

欧几里得
跟连分数,渐近分数相关.

如果数不太大的话
似乎
M M' = 1 mod N;  (N,M) = 1;
M' =  M^(N - 2) 似乎也能勉强能用用.
只是不知道高手用的是什么方法.

B9-408

2# knate
谢谢！试下

gxqcn

模逆算法一般是通过扩展欧几里得算法得到，效率也比较高。
至于2#说M' =  M^(N - 2) ，这需要已知M为素数时才能确保成立。

zgg___

我来解释一下这个问题吧，呵呵。
楼主要求x^(-1)=a mod(n)，已知n和a，求x。这里有一个小的假设藏在里面，就是a和n是互质的，如果不互质，那么问题的答案是“无”。
在互质有解的时候，问题等价于：求ax=1 mod(n)；又等价于求ax=kn+1，也可以写做求ax+nt=1的整数解，其中已知a和n，求x和t。（当然求出t后，我们无视它就可以了。）
我们假设n=am+b，也就是说m是n/a的商，b是n/a的余数，这时问题变成了ax+(am+b)t=1，即求a(x+mt)+bt=1的整数解，其中已知a和b，求x+mt和t。求出x+mt和t后，因为m已知，然后还是可以求出x和t的。可以看到，如果把x+mt和t看作新的变量，问题就恢复成原先的问题了，只是其中的两个已知量比原先小了。
这样反反复复，如果a和n是互质的，总有一天两个已知量会有一个变成1的，这时就可以直接求解了。
两个已知量缩小的速度是很快的，所以算法是高效的。如果a和n不互质，算法也会给出公因数，从而提示的。
总结一下：在这种“扩展的辗转相除法”中，上面的“m是n/a的商，b是n/a的余数”是“相除”，“问题就恢复成原先的问题了”和“这样反反复复”是“辗转”，“求出x+mt和t后，因为m已知，然后还是可以求出x和t的。”是“扩展的”。所以总的过程就是先辗转相除，然后再往回捣腾。