C# Chức năng ModInverse

Question

Có chức năng tích hợp nào cho phép tôi tính toán nghịch đảo mô đun của (mod n) không? ví dụ: 19^-1 = 11 (mod 30), trong trường hợp này là 19^-1 == -11 == 19;

Answer 1

Không có gì được tích hợp trong C# để hỗ trợ số học mô-đun. Bạn cần tự mình thực hiện, hoặc vẫn tốt hơn, hãy tìm một thư viện.

Answer 2

BouncyCastle Thư viện mật mã có triển khai BigInteger có hầu hết các chức năng số học mô-đun. Nó nằm trong không gian tên Org.BouncyCastle.Math.

Answer 3

Kể từ Net 4.0 + thực hiện BigInteger với một mô-đun arithmetics đặc biệt hoạt ModPow (trong đó sản xuất “X điện Y modulo Z”), bạn không cần phải có thư viện của bên thứ ba để thi đua ModInverse. Nếu n là số nguyên tố, tất cả các bạn cần làm là để tính toán:

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

Để biết thêm chi tiết, hãy tìm trong Wikipedia: Modular multiplicative inverse, phần Using Euler's theorem, trường hợp đặc biệt “khi m là số nguyên tố”. Nhân tiện, có một chủ đề SO gần đây hơn về vấn đề này: 1/BigInteger in c#, với cùng cách tiếp cận 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; 
     }