两数除法模

Question

我们知道

(A + B) % P = (A % P + B % P) % P
(A * B) % P = (A % P * B % P) % P

P素数在哪里？

我需要计算(A / B) % P哪里A,B可能很大并且可能溢出。

这样的模块化算术公式对(A / B) % P和成立(A - B) % P。

如果不是，请说明正确答案。

即是真的(A / B) % P = ((A % P) / (B % P)) % P吗？

我正在尝试计算（N *（N ^ 2 + 5）/ 6）％P，其中N可以大到10 ^ 15

这里A = n *（n ^ 2 + 5）肯定会在n = 10 ^ 15时溢出

Answer 1

是的，但是有所不同：

(a - b) mod p = ((a mod p - b mod p) + p) mod p

(a / b) mod p = ((a mod p) * (b^(-1) mod p)) mod p

哪里b^(-1) mod p是模逆的bMOD
p。对于p = prime，b^(-1) mod p = b^(p - 2) mod p。

编辑：

（N *（N ^ 2 + 5）/ 6）％P

您不需要任何模块化逆函数。只是简化分数：N or N^2+5将被2和整除3。因此，将它们分开，然后就可以了(a*b) mod P。