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上试过，结果也是一样的错误。

Answer 1

这是因为使用 math 模块实际上只是 Python 对 C 语言数学库的一个封装，而 C 语言的数学库不支持任意精度的数字。这意味着 math.pow(54,137) 计算的是 54 的 137 次方，但它是以 64 位浮点数的形式来计算的，这样就无法准确地表示这么大的数字的所有位数。你可以试试下面的方法，使用 Python 自带的支持任意精度的整数：

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

Answer 2

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

math.pow 是浮点数运算。你可能不想用这个。浮点数的有效数字精度不到17位，而54的137次方有237位数字。