如何将 pow 函数的结果乘以 Python 中的模数

Question

我想在 Python 中执行以下计算：

h^r * m mod p

这个计算中的所有变量都是非常大的数字。如果数字不是那么大，此公式将起作用：

c2 = (pow(pk,r) * m) % p

但是因为数字太大，这让我的机器挂了。因此，自然的解决方案是包含 pow 函数的第三个参数，以在该计算中包含模数。这计算得非常快：

pow(pk,r,p)

^ 但是，在计算模数之前，我如何调整上面的公式以将 pk^r 的结果乘以 m？

Answer 1

您可以使用以下算法，当指数为奇数时，您将底数与自身相乘。
然后您知道它是偶数并且可以除以 2，然后将底数与自身相乘。
你这样做是因为它将计算次数除以 2。
示例如下：

base = 4
exp = 12
mod = 7
m = 8
result = 1
while exp>0:
    if exp%2==0:
        result = (result*base)%mod
    base = (base*base)%mod
    exp = exp//2
print((m*result)%mod)

或者你可以在 pow 函数中使用第三个参数，像这样：(pow(base, exp, mod)*m)%mod

Answer 2

中的代码不正确。它缺少一个重要的部分；将 exp 除以 2；

base = 4
exp = 12
mod = 7
m = 8
result = 1
while exp>0:
    if exp%2==0:
        result = (result*base)%mod
    base = (base*base)%mod
    exp = exp //2
print((m*result)%mod)

当缺少 exp = exp //2 时，它将永远运行，因为 exp>0 将永远正确。

如果库中有函数，我们不建议您自己编写函数。 Python 中已经有一个（实际上是您与 an optional third parameter 一起使用的那个）；

pow(base, exp, mod)

Parameter	Description
base	A number the base
exp	A number, the exponent
mod	Optional. A number, the modulus

这个库已经使用蒙哥马利模乘技术为您处理了这个问题，如果幂不小，它比标准的重复平方更好。

pow(base, exp, mod) * m % mod

随便用。

既然是加密，那还得说需要一个secure modular exponentiation against side-channel attacks. GNU/GMP has already mpz_powm_sec for this purposes. You can access this with gmpy2模块。

如何将 pow 函数的结果乘以 Python 中的模数

How to mutiply the result of the pow function before the modulus in Python

python

encryption

pow