返回信息流即在有限域P内，设1大数为N，求其倒数M=(N^(-1))Mod(P)
这是一条镜像帖。来源：北邮人论坛 / security / #24340同步于 2009/9/21
该镜像源已超过 30 天没有更新，可能在源站已被删除。
Security机器人发帖
[求助]在有限域中如何求一个大数的倒数啊？
FlyingSnow
2009/9/21镜像同步1 回复
订阅后，新回复会通过你的通知中心匿名送达。
1 条回复
求有限域的乘法逆元（倒数），这还真是加密算法程序里面的常见问题。
通常的方法是：用扩展欧几里德算法来求乘法逆元。我偷懒，直接给个链接：
《RSA算法中的欧几里德算法》
http://blog.csdn.net/xuanshayuan/archive/2008/03/14/2181807.aspx
然后我再给出我自己的求乘法逆元算法：利用费马小定理。
根据费马小定理，如果p是质数，x不为零，那么x^(p-1) mod p = 1。
因此，x的乘法逆元就是x^(p-2) mod p。
我的算法比欧几里德算法好的地方是：运算简单，只有乘方取模，不需要一步步回推。
假如p是梅森质数，那就更好了，彻底脱离了除法运算，只要乘法和加法就够了。无论是编写程序代码还是搭建硬件电路，都会简单得多，性能也比普通算法好得多。