Fonction C # ModInverse

Est-il construit en fonction qui me permettrait de calculer l'inverse modulaire de a(mod n)?
par exemple, 19^-1 = 11 (mod 30), dans ce cas la 19^-1 == -11==19;

source d'informationauteur Nook

  1. 13

    Depuis .Net 4.0+ met en œuvre BigInteger avec une spéciale de l'arithmétique modulaire fonction ModPow (qui produit des “X puissance Y modulo Z”), vous n'avez pas besoin d'une bibliothèque tierce pour émuler ModInverse. Si n est un nombre premier, tout ce que vous devez faire est de calculer:

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

    Pour plus de détails, regardez dans Wikipédia: Modulaire inverse multiplicatifsection En utilisant le théorème d'Eulerle cas particulier “lorsque m est un nombre premier”. Par ailleurs, il existe une plus récente, DONC sujet sur ce: 1/BigInteger en c#avec la même approche proposé par CodesInChaos.

  2. 5
    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;
}
  3. 2

    La BouncyCastle bibliothèque Crypto a un BigInteger de mise en œuvre qui a le plus de l'arithmétique modulaire fonctions. C'est dans le Org.BouncyCastle.Les mathématiques de l'espace de noms.

  4. 1
    BigInteger modInverse(BigInteger a, BigInteger n)
        {
            BigInteger i = n, v = 0, d = 1;
            while (a > 0)
            {
                BigInteger 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;
        }
  5. 0

    Il n'y a rien de construit en C# à l'appui de l'arithmétique modulaire. Vous devez le faire vous-même, ou mieux encore, trouver une bibliothèque.

  6. 0

    Il n'y a pas de bibliothèque pour arriver inverse de mod, mais le code suivant peut être utilisé pour l'obtenir.

    //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;
        }
}