关于pow(base, exp[, mod])
函数的文档中说,
"如果mod
存在并且exp
为负,则base
必须是相对素数以进行mod。在这种情况下,返回pow(inv_base, -exp, mod)
,其中inv_base
是base
模mod
的逆">
我根本不懂这条线,也不懂它是怎么工作的。提供的示例如下:
>>> 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_ 333(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 == 1
和874/38=23
。所以最后的表达式变成:
23 * 38 % 97 == 1
因此,答案是23。