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;C# Chức năng ModInverse
Trả lời
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.
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.
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.
Xin lưu ý rằng đó là trường hợp đặc biệt, * khi m là số nguyên tố *. –
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;
}
Dường như hoạt động, nhưng sẽ tốt nếu nó có thể báo hiệu (ví dụ như ném một ngoại lệ) nếu nghịch đảo là không thể ('a' không thể nghịch đảo' n') xảy ra khi 'a' và' n' chia sẻ yếu tố không tầm thường (GCD của họ vượt quá một). –
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;
}
Được bình chọn là bản sao của Samuels (có định dạng xấu) với câu trả lời được thay bằng BigInteger. –
Lưu ý rằng bạn có thể đảo ngược các phép nhân tùy ý. Ví dụ 2 có đa thức nghịch đảo modulo 30 kể từ GCD (2,30)! = 1 – CodesInChaos