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的扩展欧几里德算法！！！！！！！！！
页: [1]
查看完整版本: 大整数模逆算法