Python pow()函数如何使用负幂和mod值



关于pow(base, exp[, mod])函数的文档中说,
"如果mod存在并且exp为负,则base必须是相对素数以进行mod。在这种情况下,返回pow(inv_base, -exp, mod),其中inv_basebasemod的逆">

我根本不懂这条线,也不懂它是怎么工作的。提供的示例如下:

>>> pow(38, -1, mod=97)
23
>>> 23 * 38 % 97 == 1
True

它不应该表现为(38**-1(%97=0.02631578947368421吗
如果我尝试从23 * 38 % 97 == 1向后,我不知道模的逆是什么。

有人能给我一个明确的解释吗?数学解释会很有帮助。

在模算术中,除法没有唯一的答案,所以我们没有除法运算。相反,你有模逆。

文献试图解释pow(b, -1, mod=m)可以用于计算b的逆,模m。也就是说,求一些数d,使得d * b % m = 1

线23 * 38 % 97 == 1简单地证明了作为pow(38, -1, mod=97)的结果的答案23是38的正确模逆。

文档中的解释似乎是假设读者已经对模块算术有了一些熟悉。

有人能给我一个明确的解释吗?数学解释会很有帮助。

尝试运行以下代码片段:

for i in range(97): 
s = f"{i} * 38 % 97" 
print(s, "==", eval(s))

恰好其中一条线将揭示同余CCD_ 17。当然,有更聪明的方法来计算倒数,但上面的强力演示应该更容易理解模块倒数的含义。

在指定了整数参数和mod的情况下,pow()在"模CCD_ 20的乘性整数群";

例如,与8相对素数的整数(1、3、5和7(在乘法mod 8下形成一个群。标识为1。由于3*3=9与1模8全等,因此3在该群中是其自身的逆,并且

>>> pow(3, -1, 8)
3

在doc示例中,23和38是模97的逆。

>>> pow(23, -1, 97)
38
>>> pow(38, -1, 97)
23

这并不是特别深奥,而是数论中的基本工具。

@wim的回答和@Tim Peters的例子帮助我理解这个pow()函数中发生了什么。举个例子,

>>> pow(3, -1, 8)
3

编号为m的模必须在range(0,m)中。例如,14%5必须在range(0,5)中,因此它是4。

所以模1/3 % 8必须在range(8)中。但作为不在范围内的1/3=0.33,我们需要一种方法来找到它。

1/3 % 8不能为零,因为它不可分割。因此,可能的最低值是1。这意味着,我们需要以x % 8 == 1变为True的方式来表示1/3。CCD_ 33
3(target value) * 3(base) = 9,因此,答案为3(目标值(。

对于一个复杂的例子,让我们举一个例子:

>>> pow(38, -1, mod=97)
23

CCD_ 35。再说一遍,需要一条出路。由于最低mod应该是1,因此x % 97 == 1。显然98 % 97 == 1,但98/38不是一个整数。接下来,(2*97+1(或195 % 97 == 1,但195/38不是整数。

在此过程中,(9*97+1(或874 % 97 == 1874/38=23。所以最后的表达式变成:

23 * 38 % 97 == 1

因此,答案是23。

最新更新