x*x mod(p) 最有效的 pythonic 方式？

Question

在 python 中执行 x = x*x mod(p) 的最有效方法是什么：（我知道 x < p）

x = pow(a, 2, p)

或

x = x*x % p

或

x *= x
x %= p

（我认为如果用效率来衡量的话x*x和x**2是一样的，如果不行就修我）

Answer 1

Python 有一个 timeit 模块用于测试这类事情：

$ python -m timeit 'x = 2000; p = 2002; x = pow(x, 2, p)'
10000000 loops, best of 3: 0.115 usec per loop
$ python -m timeit 'x = 2000; p = 2002; x = (x * x) % p' 
10000000 loops, best of 3: 0.0542 usec per loop
$ python -m timeit 'x = 2000; p = 2002; x *= x; x %= p' 
10000000 loops, best of 3: 0.0614 usec per loop

你的回答是(x * x) % p和x *= x; x %= p差不多，但是pow慢很多。

x*x mod(p) 最有效的 pythonic 方式？

x*x mod(p) most efficient pythonic way?

python

modulo