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

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

额，事情较多，忘记上来看了！谢谢哈！

账号		自动登录	找回密码
密码			欢迎注册

[求助] 如何计算一个素数的模逆？

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。