Python 取模结果不正确。

Question

我完全被难住了。我正在使用以下值计算RSA中数字54的密码：

p=5; q=29; n=145 d=9; e=137

因此，加密数字54将是：

54^137 mod 145

或在Python中等价于：

import math
math.pow(54,137)%145

我的计算器给出的结果是24，而我在Python中运行的语句给出的结果是54.0。很明显Python的结果是错误的，但我不知道为什么或者如何解决。请在你的Python安装上尝试一下。我使用的版本是2.5.1，但我也尝试了2.6.5，结果都是错误的。

- Franz

Answer 1

>>> pow(54,137,145)
24

math.pow 是浮点数。你不想用它。浮点数的有效精度不到17位。54 ** 137有237位。

- S.Lott

---

谢谢！有趣的信息，我喜欢学习这样的小细节。 - Franz

@Franz：“小细节”？像浮点数只表示几个小数位的精度？我认为这不仅仅是小细节。有相当数量的SO问题反映其他人不知道这个信息。或者你指的是其他东西？ - S.Lott

Answer 2

这是因为使用math模块基本上只是Python对C数学库的封装，而C数学库没有任意精度数字。这意味着math.pow(54,137)将54^137作为64位浮点数进行计算，这意味着它不足以容纳如此大的数字的所有位数。相反，尝试使用Python的正常内置任意精度整数：

>>> (54 ** 137) % 145
24L

- user470379

---

对于模算术，使用带有3个参数的pow(x, y, z)而不是x ** y % z通常是一个非常好的选择 - 这避免了必须创建可能巨大的中间值x ** y的需求。 - ncoghlan