Is the开发者_运维问答re 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;
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.
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;
}
The BouncyCastle Crypto library has a BigInteger implementation that has most of the modular arithmetic functions. It's in the Org.BouncyCastle.Math namespace.
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;
}
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;
}
}
精彩评论