3

我在寻找除法模数时被困在一个程序中。

比如说我有：

((a*b*c)/(d*e)) % n

现在，我不能简单地计算表达式，然后将其取模到 n，因为乘法和除法是在一个循环中进行的，并且该值足够大，即使是 long long 也不适合。

正如评论中所阐明的，n 可以被认为是素数。

我发现，对于乘法，我可以很容易地将其计算为：

((a%n*b%n)%n*c%n)%n

但当时不明白如何计算除法部分。

我面临的问题是一个简单的例子：

((7*3*5)/(5*3)) % 11

上述表达式的值为 7

但如果我计算乘法，模，它会像：

((7%11)*(3%11))%11 = 10
((10%11)*(5%11))%11 = 6

现在我只剩下 6/15，我无法生成正确的答案。

有人可以帮助我。请通过上面的例子让我理解逻辑。

4

7 回答 7

5

因为 11 是素数，所以Z 11是一个域。因为15 % 11is 4，1/15等于3（因为3 * 4 % 11是 1）。因此，6/15是6 * 3哪个是7mod 11。

在问题下方的评论中，您澄清了模数始终是素数。

为了有效地生成乘法逆表，您可以提高2连续幂以查看它生成的值。请注意，在域Z p中，其中 p 是奇素数，2 p-1 = 1。因此，对于Z 11：

 2^1 = 2
 2^2 = 4
 2^3 = 8
 2^4 = 5
 2^5 = 10
 2^6 = 9
 2^7 = 7
 2^8 = 3
 2^9 = 6

所以5（2 4）的乘法逆元是2 6（9）。

因此，您可以像这样生成上表：

power_of_2[0] = 1;
for (int i = 1; i < n; ++i) {
    power_of_2[i] = (2*power_of_2[i-1]) % n;
}

乘法逆表可以这样计算：

mult_inverse[1] = 1;
for (int i = 1; i < n; ++i) {
    mult_inverse[power_of_2[i]] = power_of_2[n-1-i];
}
于 2013-07-09T22:01:12.447 回答
2

由于 n 是素数，除以整数 b 只是乘以 b 的倒数。那是：

(a / b) mod n = (a * inv(b)) mod n

在哪里

inv(b) = (b ^ (n - 2)) mod n

计算 inv(b) 可以通过平方算法在 O(log(n)) 时间内完成。这是代码：

int inv(int b, int n)
{
    int r = 1, m = n - 2;
    while (m)
    {
        if (m & 1) r = (long long)r * b % n;
        b = (long long)b * b % n;
        m >>= 1;
    }
    return r;
}

为什么它有效？根据费马小定理，如果 n 是素数，对于任何正整数 b，b ^ (n - 1) mod n = 1。因此我们有 inv(b) * b mod n = 1。

寻找 inv(b) 的另一个解决方案是扩展欧几里得算法，它需要更多的代码来实现。

于 2013-07-11T03:50:54.903 回答
2

在您的示例中，由于 15 = 4 mod 11，您实际上最终不得不评估 (6/4) mod 11。

为了找到一个精确的解决方案，将其重新排列为 6 = ( (x * 4) mod 11)，这使得模除法的工作原理更加清晰。

如果没有别的，如果模数总是很小，您可以从 0 迭代到模数-1 以获得解决方案。

请注意，当模数不是素数时，可能有多种解决方案来解决约化问题。例如，4 = ( ( x * 2) mod 8) 有两种解决方案：2 和 6。这将发生在形式简化的问题中：

  a = ( (x * b) mod c)

每当 b 和 c 不是互质时（即，只要它们确实共享一个公约数）。

类似地，当 b 和 c 不是互质时，可能无法解决约化问题。例如，3 = ( (x * 2) mod 8) 没有解。每当b 和 c的最大公约数不整除 a 时，就会发生这种情况。

后两种情况是从 0 到 n-1 的整数在 n不是素数时不形成乘法下的群（或等效地，在 + 和 * 下的域）的结果，而是简单地形成环的不太有用的结构。

于 2013-07-09T22:14:42.443 回答
2

我认为提出问题的方式应该假设分子可以被分母整除。在这种情况下，素数 n 的有限域解以及关于非素数 n 的可能扩展和警告的推测基本上是矫枉过正。如果您将所有分子项和分母项都存储在数组中，则可以迭代测试（分子项，分母项）对并快速找到最大公约数（gcd），然后将分子项和分母项除以gcd . （寻找 gcd 是一个经典问题，你可以很容易地在网上找到一个简单的解决方案。）在最坏的情况下，你将不得不迭代所有可能的对，但在某些时候，如果分母确实除以分子，那么你最终会留下减少的分子项，所有分母项都为 1。

于 2013-07-10T15:44:09.980 回答
0

我认为您可以像这样分配部门

z = d*e/3
(a/z)*(b/z)*(c/z) % n

剩下的只是整数除法问题。

于 2013-07-09T21:59:34.690 回答
0

与其除法，不如从乘法逆元的角度来思考。对于 mod-n 系统中的每个数字，如果满足某些条件，则应该有一个倒数。对于 d 和 e，找到那些倒数，然后一切都只是相乘。求逆不是通过除法完成的！那里有很多信息...

于 2013-07-09T22:16:38.673 回答
0

我认为您遇到的问题是您选择了一个对于示例来说太简单的问题。在那种情况下，答案是 7 ，但如果 a*b*c 不能被 c*d 整除怎么办？您可能应该先查看如何使用模数进行除法，您应该很清楚:)

于 2013-07-09T22:04:50.000 回答