C# ModInverse 函数
是否有一个内置函数可以让我计算 a(mod n) 的模逆? 例如 19^-1 = 11 (mod 30),在这种情况下 19^-1 == -11==19;
Is there a built in function that would allow me to calculate the modular inverse of a(mod n)?
e.g. 19^-1 = 11 (mod 30), in this case the 19^-1 == -11==19;
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(5)
由于 .Net 4.0+ 使用特殊的模算术函数 ModPow 实现 BigInteger(它产生“
X
幂Y
模Z
”),因此您不需要不需要第三方库来模拟 ModInverse。如果n
是素数,您需要做的就是计算:有关更多详细信息,请查看维基百科:模乘法逆元,第 使用欧拉定理,特殊情况“当 m 是素数时”。顺便说一句,最近有一个关于此的主题: 1/BigInteger in c#,采用相同的方法建议混沌代码。
Since .Net 4.0+ implements BigInteger with a special modular arithmetics function ModPow (which produces “
X
powerY
moduloZ
”), you don't need a third-party library to emulate ModInverse. Ifn
is a prime, all you need to do is to compute:For more details, look in Wikipedia: Modular multiplicative inverse, section Using Euler's theorem, the special case “when m is a prime”. By the way, there is a more recent SO topic on this: 1/BigInteger in c#, with the same approach suggested by CodesInChaos.
BouncyCastle Crypto 库有一个 BigInteger 实现,它具有大多数模块化算术函数。它位于 Org.BouncyCastle.Math 命名空间中。
The BouncyCastle Crypto library has a BigInteger implementation that has most of the modular arithmetic functions. It's in the Org.BouncyCastle.Math namespace.
这是 Samuel Allan 的算法的稍微完善的版本。
TryModInverse
方法返回一个bool
值,该值指示该数字和模是否存在模乘逆。Here is a slightly more polished version of Samuel Allan's algorithm. The
TryModInverse
method returns abool
value, that indicates whether a modular multiplicative inverse exists for this number and modulo.没有用于获取逆模的库,但可以使用以下代码来获取它。
There is no library for getting inverse mod, but the following code can be used to get it.