两数除法模 [英] Modulo of Division of Two 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是真的吗?

我试图计算(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

这里，对于n = 10 ^ 15，A = n *(n ^ 2 + 5)肯定可以溢出

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) mod p是b mod p的模逆.对于p = prime，b^(-1) mod p = b^(p - 2) mod 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 or N^2+5将被2和3整除.因此，将它们分开，便得到(a*b) mod 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.

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