在 C# 中求解模

Question

我在用 C# 求模时遇到问题。下面的例子

7^-1 modulo 26

启用 Wolfram Alpha returns 正确 15。在 c# 中，当我直接尝试时：

1/7 % 26

它 returns 不需要 0.142857142857143 而不是想要的 15。但我不是数学大师，所以我可能遗漏了一些重要的东西。

Answer 1

您正在寻找模反演：以防

7**-1 modulo 26 = x

或

1 / 7 modulo 26 = x

你实际上想找出一个x使得

(x * 7) modulo 26 = 1

在我们的案例中 x == 15 因为

 15 * 7 == 105 == 26 * 4 + 1

对于 small modulo 值（如 26），您可以在 [=50 的帮助下找到答案（15） =]天真 for 循环：

  int modulo = 26;
  int div = 7;
  int result = 0;
  
  for (int i = 1; i < modulo; ++i)
    if ((i * div) % modulo == 1) {
      result = i;

      break;
    }

  Console.Write(result);

一般情况下，可以借助Extended Euclid Algorithm获得result。通常，在使用模运算时，我们会遇到巨大的数字，这就是为什么让我展示 BigInteger 的代码；如果不是你的情况，你可以把 BigInteger 变成好旧的 int.

代码：

using System.Numerics;
...
private static (BigInteger LeftFactor,
                BigInteger RightFactor,
                BigInteger Gcd) Egcd(this BigInteger left, BigInteger right) {
  BigInteger leftFactor = 0;
  BigInteger rightFactor = 1;

  BigInteger u = 1;
  BigInteger v = 0;
  BigInteger gcd = 0;

  while (left != 0) {
    BigInteger q = right / left;
    BigInteger r = right % left;

    BigInteger m = leftFactor - u * q;
    BigInteger n = rightFactor - v * q;

    right = left;
    left = r;
    leftFactor = u;
    rightFactor = v;
    u = m;
    v = n;

    gcd = right;
  }

  return (LeftFactor: leftFactor,
          RightFactor: rightFactor,
          Gcd: gcd);
}

反转本身将是

private static BigInteger ModInversion(BigInteger value, BigInteger modulo) {
  var egcd = Egcd(value, modulo);

  if (egcd.Gcd != 1)
    throw new ArgumentException("Invalid modulo", nameof(modulo));

  BigInteger result = egcd.LeftFactor;

  if (result < 0)
    result += modulo;

  return result % modulo;
}

演示：

using System.Numerics;

...

BigInteger result = ModInversion(7, 26);

Console.Write(result);

结果：

在 C# 中求解模

Solving modulo in c#

c#

algorithm

modulo

modulus

mod