silitex 发表于 2015-12-22 15:58:37

如何计算一个素数的模逆？

我手动找到了3之于256的模逆：171。举例比如：
(1 * 3) MOD 256 = 3 <==> (3 * 171) MOD 256 = 1
(2 * 3) MOD 256 = 6 <==> (6 * 171) MOD 256 = 2
(3 * 3) MOD 256 = 9 <==> (9 * 171) MOD 256 = 3
(11 * 3) MOD 256 = 33 <==> (33 * 171) MOD 256 = 11
(188 * 3) MOD 256 = 52 <==> (52 * 171) MOD 256 = 188
(255 * 3) MOD 256 = 253 <==> (253 * 171) MOD 256 = 255

我的问题是，比如给定一个素数n和求模数m，如何通过一个公式或者算法快速求得n的模逆o(或者发现不存在模逆)？
除了枚举法，实在想不到有什么通用的解法。

manthanein 发表于 2015-12-22 20:42:48

虽然我不懂，不过可以查到一些参考资料
http://wenku.baidu.com/view/df000a896529647d2728520a.html

liangbch 发表于 2015-12-23 07:35:08

扩展欧几里得算法

silitex 发表于 2015-12-25 16:12:37

额，事情较多，忘记上来看了！谢谢哈！
页: [1]
查看完整版本: 如何计算一个素数的模逆？