如何计算模数除法

Question

在找到除法模数时,我被困在一个程序中.

比方说我有:

((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,我无法生成正确的答案.

有人能帮助我吗 请通过上面的例子让我理解逻辑.

Answer 1

由于11是素数,Z ₁₁是场.因为15 % 11是4,1/15等于3(从3 * 4 % 111开始).因此,6/15是6 * 3其为7模11.

在你的问题下面的评论中,你澄清了模数永远是一个素数.

要有效地生成乘法逆的表,您可以提高2到连续的幂以查看它生成的值.注意,在字段Z _p中,其中p是奇素数,2 ^p-1 = 1.因此,对于Z ₁₁:

 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 ⁴)的乘法逆是2 ⁶(即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];
}