C# ModInverse Function

Question

Esiste una funzione incorporata che consenta di calcolare l'inverso modulare di una (mod n)? ad es. 19^-1 = 11 (mod 30), in questo caso il 19^-1 == -11 == 19;

Answer 1

Non c'è niente di integrato in C# per supportare l'aritmetica modulare. Devi implementarlo tu stesso, o meglio ancora, trovare una biblioteca.

Answer 2

Il BouncyCastle libreria Crypto dispone di un'implementazione BigInteger che ha la maggior parte delle funzioni aritmetiche modulari. È nello spazio dei nomi Org.BouncyCastle.Math.

Answer 3

Dal .Net 4.0 + implementa BigInteger con una speciale aritmetica modulare funzionano ModPow (che produce “X potere Y modulo Z”), non hai bisogno di una libreria di terze parti di emulare ModInverse. Se n è un numero primo, tutto quello che dovete fare è quello di calcolare:

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

Per maggiori dettagli, guardare in Wikipedia: Modular multiplicative inverse, sezione Using Euler's theorem, il caso particolare “quando m è un numero primo”. A proposito, c'è un argomento SO più recente al riguardo: 1/BigInteger in c#, con lo stesso approccio suggested by CodesInChaos.

Answer 4

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

Answer 5

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