两个数字划分的模数

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.

Answer 2

弗拉德的答案是正确的：

(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

这些和其他一些操作在“ 等效性”部分中概述。

只是想让您知道，这不仅适用于素数p。第一个将适用于任何p。第二个将任何工作p，其中b^(-1)或模逆被定义。

可以使用扩展的Euclidian算法来计算模逆