司ofTwo数的模 [英] Modulo of Division ofTwo Numbers

问题描述

我们知道

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

其中， P 是一个素数。

我需要计算（A / B）％，P ，其中 A，B 可以是非常大的，能溢出。

I need to calculate (A / B) % P where A,B can be very large and can overflow .

请问这类公式的模块化运算保持着（A / B）％，P 和（A - B）％，P 。

Does such kind of formula for modular arithmetic holds for (A / B) % P and (A - B) % P.

如果没有，那么请说明正确的答案是什么。

If not then please explain what the correct answer is.

即是真的，（A / B）％，P =（（A％P）/（B％P））％，P ？

我试图CALULATE（N *（N ^ 2 + 5）/ 6）％P其中N可以是大到10 ^ 15

I WAS TRYING TO CALULATE (N*(N^2+5)/6)%P where N can be as large as 10^15

这里A = N *（N ^ 2 + 5）一定能够溢出N = 10 ^ 15

here A=n*(n^2+5) can surely overflow for n=10^15

推荐答案

是的，但它是不同的：

(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）模p 的模逆 B > MOD P 。对于 P =素， B ^（ - 1）模p = B ^（P - 2）模p 。

Where b^(-1) mod p is the modular inverse of b mod p. For p = prime, b^(-1) mod p = b^(p - 2) mod p.

编辑：

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

(N*(N^2+5)/6)%P

您不需要任何与此模块化逆。只是简化了部分： N或N ^ 2 + 5 将整除 2 和 3 。因此，将它们，然后你有（A * B）模p 。

You don't need any modular inverses from this. Just simplify the fraction: N or N^2+5 will be divisible by 2 and 3. So divide them and then you have (a*b) mod P.

这篇关于司ofTwo数的模的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！