algorithm - 模运算 (a*b/e)%m?

Question

以下是否有可能的模块化表达式：

((a*b)/e)%m

例如：

(a*b*c)%m = ((a%m)*(b%m)*(c%m))%m

Answer 1

使用模算术时不必执行除法，而是必须乘以模逆。例如，要除以e，您将乘以模逆c，其中c × e ≡ 1 (mod m )。您可以通过以下算法计算x (mod m )的模逆：

function inverse(x, m)
    a, b, u = 0, m, 1
    while x > 0
        q = b // x # integer division
        x, a, b, u = b % x, u, x, a - q * u
    if b == 1 return a % m
    error "must be coprime"

因此，对于您的表达式，((a*b)/e)%m您将计算(a * b * inverse(e,m)) % m.

Answer 2

这取决于您对除法的含义；例如对于

a = 1
b = 1
e = 3
m = 7

你期望的结果是什么？1/3 通过传统算术计算为 0，如果在这种情况下您正在寻找它，那么通常没有捷径（但是，如果a*b已知足够小，您可以将除法换成乘法和移位）。

然而，除法的另一种选择是在模算术x/y中寻找乘以y给出的数字（并且这个含义是因为在考虑模7时是1）。如果这是您要寻找的而不是除以，则可以乘以ie 的模逆，乘以得到 1 (mod ) 的数字。x1/355*3eeem