Python modulus result is incorrect

I am totally stumped. I was computing the cipher of the number 54 in RSA with the following values:

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

So the number 54 encrypted would be:

54^137 mod 145

or equivalently in p开发者_StackOverflow中文版ython:

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

My calculator gives me 24, my python statement gives me 54.0. Python is clearly wrong but I have no idea why or how. Try it on your installations of Python. My version is 2.5.1 but I also tried on 2.6.5 with the same incorrect result.

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

math.pow is floating point. You don't want that. Floating-point values have less than 17 digits of useful precision. The 54**137 has 237 digits.

That's because using the math module is basically just a Python wrapper for the C math library which doesn't have arbitrary precision numbers. That means math.pow(54,137) is calculating 54^137 as a 64-bit floating point number, which means it will not be precise enough to hold all the digits of such a large number. Try this instead to use Python's normal built-in arbitrary precision integers:

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