C＃ModInverse関数

Question

a（mod n）のモジュラ逆数を計算できるようにする組み込み関数はありますか？例： 19^-1 = 11（mod 30）、この場合は19^-1 == -11 == 19;

Answer 1

モジュラ演算をサポートするためにC＃には何も組み込まれていません。あなたはそれを自分で実装する必要がありますが、それでもなおライブラリを見つける必要があります。

Answer 2

BouncyCastle暗号ライブラリには、ほとんどのモジュラ算術関数を持つBigInteger実装があります。 Org.BouncyCastle.Math名前空間にあります。ネット4.0+は特別合同算術でのBigIntegerを実装しているため

Answer 3

は（「XパワーY剰余Z」を生成）ModPowは、あなたがModInverseをエミュレートするために、サードパーティのライブラリを必要としない機能します。 nが素数である場合は、あなたがする必要があるすべては計算することである。詳細については

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

、ウィキペディアで見て：Modular multiplicative inverse、セクションUsing Euler's theorem、特殊なケース「mが素数であるとき」。ちなみに、最近のSOの話題は1/BigInteger in c#で、同じアプローチで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; 
     }