大整数模逆算法

gxqcn · 发表于 2008-8-5 08:59:10

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

您需要登录才可以下载或查看，没有账号？欢迎注册

×

已知无符号大整数 $a, m$，求整数 $x$，使之 $ax \equiv 1 (mod m), 0<x<m$ 成立。
上述过程称为计算大整数模逆（注意，当 $gcd(a, m) != 1$ 时无解）。

一般常用的算法是借助于扩展欧几里德算法求模逆，
但这样原本可以在无符号领域内可以解决的问题，不得不引入符号。

所以，请大家提供上佳的模逆算法，
不论是提供相关链接、还是直接上传论文，中英文不限。谢谢大家！

模逆算法在计算数论中非常重要，对其的研究一直未停止过。

gxqcn · 发表于 2008-8-5 09:49:51

在公司的电脑里我曾下载有一份比较有价值的论文，
可惜今天请假在家，刚才在硬盘里没找到，改天传上来。

gxqcn · 发表于 2008-8-13 19:16:02

上传两篇。
还有一篇比较好，可惜文件偏大了。

kevinuouo · 发表于 2010-9-14 14:16:10

3# gxqcn

多谢谢~~~

flyliying · 发表于 2012-4-24 10:03:25

模逆是用穷举法吗

gxqcn · 发表于 2012-4-24 10:14:10

大整数算法，用穷举法显然不适用。

knate · 发表于 2012-6-1 20:50:44

费马小定理似乎可以.
但是似乎欧拉函数不是很好求,
除非是个m是个素数或者是个高复合数.
在特殊场合会有用.

另外曾看到一篇文章,
似乎是经过适当变换以后,
可以转换成求 my = 1 (mod a)
当a,m位数相差较大时有用.
这是应用在单片机还是FPGA上的技术.
具体的得找找那文档扔哪里去了.
似乎是中科院的一篇论文.

liuyun242 · 发表于 2012-8-21 12:58:09

看看，我有lisp的扩展欧几里德算法！！！！！！！！！

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

[求助] 大整数模逆算法

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

评分

评分