C# ModInverse Funktion

Gibt es eine eingebaute Funktion, die mir erlauben würde, berechnet das modulare inverse von a(mod n)?
z.B. 19^-1 = 11 (mod 30), in diesem Fall die 19^-1 == -11==19;

Beachten Sie, dass Sie umkehren können beliebige Multiplikationen. Für Beispiel 2 ist multiplikative inverse modulo 30, da GCD(2,30)!=1

InformationsquelleAutor Nook | 2011-09-20

  1. 13

    Da .Net 4.0+ implementiert BigInteger mit einem speziellen modularen Arithmetik-Funktion ModPow (was produziert "X macht Y modulo Z"), Sie brauchen nicht eine Drittanbieter-Bibliothek zu emulieren ModInverse. Wenn n ist ein Paradebeispiel, alles, was Sie tun müssen, ist zu berechnen:

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

    Für mehr details, schauen Sie in Wikipedia: Modulare multiplikative inverse, Abschnitt Mit Euler ' s theorem, den speziellen Fall "wenn m ist eine Primzahl". By the way, gibt es eine neuere ALSO Thema: 1/BigInteger in c#, mit dem gleichen Ansatz vorgeschlagen durch CodesInChaos.

    Bitte beachten Sie, dass es den speziellen Fall, , wenn m eine Primzahl.

    InformationsquelleAutor Anton Samsonov

  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;
}
    Scheint zu funktionieren, aber es wäre schön, wenn es könnte signal (z.B. durch das werfen einer exception), wenn die inverse nicht möglich ist (a ist nicht invertierbar modulo n) was passiert, wenn a und n Aktien einen nicht-trivialen Faktor (Ihre GCD übersteigt).

    InformationsquelleAutor Samuel Allan

  3. 2

    Den BouncyCastle Crypto-Bibliothek hat ein BigInteger-Implementierung, die hat die meisten der modulare Arithmetik-Funktionen. Es ist in der Org.BouncyCastle.Math-namespace.

    InformationsquelleAutor Michael Bray

  4. 0

    Es ist keine Bibliothek für das abrufen inverse mod, aber der folgende code kann verwendet werden, um es zu bekommen.

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

    InformationsquelleAutor John P P

Schreibe einen Kommentar