C# ModInverse 函数

发布于 2024-12-05 12:05:06 字数 84 浏览 4 评论 0原文

是否有一个内置函数可以让我计算 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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(5

柏拉图鍀咏恒 2024-12-12 12:05:06

由于 .Net 4.0+ 使用特殊的模算术函数 ModPow 实现 BigInteger(它产生“XYZ”),因此您不需要不需要第三方库来模拟 ModInverse。如果 n 是素数,您需要做的就是计算:

a_inverse = BigInteger.ModPow(a, n - 2, n)

有关更多详细信息,请查看维基百科:模乘法逆元,第 使用欧拉定理,特殊情况“当 m 是素数时”。顺便说一句,最近有一个关于此的主题: 1/BigInteger in c#,采用相同的方法建议混沌代码

Since .Net 4.0+ implements BigInteger with a special modular arithmetics function ModPow (which produces “X power Y modulo Z”), you don't need a third-party library to emulate ModInverse. If n is a prime, all you need to do is to compute:

a_inverse = BigInteger.ModPow(a, n - 2, n)

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.

寂寞花火° 2024-12-12 12:05:06
int modInverse(int a, int n) 
{
    int i = n, v = 0, d = 1;
    while (a>0) {
        int t = i/a, x = a;
        a = i % x;
        i = x;
        x = d;
        d = v - t*x;
        v = x;
    }
    v %= n;
    if (v<0) v = (v+n)%n;
    return v;
}
int modInverse(int a, int n) 
{
    int i = n, v = 0, d = 1;
    while (a>0) {
        int t = i/a, x = a;
        a = i % x;
        i = x;
        x = d;
        d = v - t*x;
        v = x;
    }
    v %= n;
    if (v<0) v = (v+n)%n;
    return v;
}
梦开始←不甜 2024-12-12 12:05:06

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.

离笑几人歌 2024-12-12 12:05:06

这是 Samuel Allan 的算法的稍微完善的版本。 TryModInverse 方法返回一个 bool 值,该值指示该数字和模是否存在模乘逆。

public static bool TryModInverse(int number, int modulo, out int result)
{
    if (number < 1) throw new ArgumentOutOfRangeException(nameof(number));
    if (modulo < 2) throw new ArgumentOutOfRangeException(nameof(modulo));
    int n = number;
    int m = modulo, v = 0, d = 1;
    while (n > 0)
    {
        int t = m / n, x = n;
        n = m % x;
        m = x;
        x = d;
        d = checked(v - t * x); // Just in case
        v = x;
    }
    result = v % modulo;
    if (result < 0) result += modulo;
    if ((long)number * result % modulo == 1L) return true;
    result = default;
    return false;
}

Here is a slightly more polished version of Samuel Allan's algorithm. The TryModInverse method returns a bool value, that indicates whether a modular multiplicative inverse exists for this number and modulo.

public static bool TryModInverse(int number, int modulo, out int result)
{
    if (number < 1) throw new ArgumentOutOfRangeException(nameof(number));
    if (modulo < 2) throw new ArgumentOutOfRangeException(nameof(modulo));
    int n = number;
    int m = modulo, v = 0, d = 1;
    while (n > 0)
    {
        int t = m / n, x = n;
        n = m % x;
        m = x;
        x = d;
        d = checked(v - t * x); // Just in case
        v = x;
    }
    result = v % modulo;
    if (result < 0) result += modulo;
    if ((long)number * result % modulo == 1L) return true;
    result = default;
    return false;
}
苦笑流年记忆 2024-12-12 12:05:06

没有用于获取逆模的库,但可以使用以下代码来获取它。

// Given a and b->ax+by=d
long[] u = { a, 1, 0 };
long[] v = { b, 0, 1 };
long[] w = { 0, 0, 0 };
long temp = 0;
while (v[0] > 0)
{
    double t = (u[0] / v[0]);
    for (int i = 0; i < 3; i++)
    {
        w[i] = u[i] - ((int)(Math.Floor(t)) * v[i]);
        u[i] = v[i];
        v[i] = w[i];
    }
}
// u[0] is gcd while u[1] gives x and u[2] gives y. 
// if u[1] gives the inverse mod value and if it is negative then the following gives the first positive value
if (u[1] < 0)
{
        while (u[1] < 0)
        {
            temp = u[1] + b;
            u[1] = temp;
        }
}

There is no library for getting inverse mod, but the following code can be used to get it.

// Given a and b->ax+by=d
long[] u = { a, 1, 0 };
long[] v = { b, 0, 1 };
long[] w = { 0, 0, 0 };
long temp = 0;
while (v[0] > 0)
{
    double t = (u[0] / v[0]);
    for (int i = 0; i < 3; i++)
    {
        w[i] = u[i] - ((int)(Math.Floor(t)) * v[i]);
        u[i] = v[i];
        v[i] = w[i];
    }
}
// u[0] is gcd while u[1] gives x and u[2] gives y. 
// if u[1] gives the inverse mod value and if it is negative then the following gives the first positive value
if (u[1] < 0)
{
        while (u[1] < 0)
        {
            temp = u[1] + b;
            u[1] = temp;
        }
}
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文