列表中元素的幂

Question

我有这个示例代码：

n = 11698030645065745910098695770921
e = 9569991810443215702618212520777
d = 7874909554574080825236064017913
m = 104228568138
m = int(m)
e = int(e)
n = int(n)
def preparation(m, n):
block_lenght= len(str(n)) - 1
m = [str(m)[i:i+block_lenght] for i in range(0, len(str(m)), block_lenght)]
return m
def encrypt(m, n, e):
m = preparation(m, n)
power = [int(i) ** e for i in m]
modulo = [i%n for i in power]
total_sum = sum(modulo)
return total_sum
m = encrypt(m, n, e)
print("m = ", m)

你能告诉我为什么这个算法对这么大的数字如此缓慢吗？我怎样才能让它更快？

Answer 1

另一种方法是使用带lambda的apply-map。

http://book.pythontips.com/en/latest/map_filter.html

a_to_power_e = list(map(lambda x : int(x)**e, a))
a_modulo_n = list(map(lambda x : int(x)%n, a_to_power_e))

如果您想多次重用同一个函数，可以执行以下操作。

cust_power_func = lambda x : int(x)**e
cust_modulo_func = lambda x : int(x)%n
a_to_power_e = list(map(cust_power_func, a))
a_modulo_n = list(map(cust_modulo_func, a_to_power_e))

Answer 2

您可以首先使用内置的pow函数或使用**运算符创建列表power。两种实现方式见下文：

In [1777]: n = 43787
...: e = 31
In [1778]: a
Out[1778]: ['1112', '2222', '3323', '4']
In [1781]: power = [pow(int(i),e) for i in a]

或

In [1786]: power = [int(i) ** e for i in a]

然后，在上面创建的功率列表的每个元素上创建另一个列表modulo：

In [1784]: modulo = [i%n for i in power]
In [1785]: modulo
Out[1785]: [19378L, 27732L, 26928L, 30208]

创建了另一个函数来计算power。尝试检查性能是否随以下内容而提高：

MOD = 1000000007
def fast_power(base, power):
result = 1
while power > 0:
# If power is odd
if power % 2 == 1:
result = (result * base) % MOD
# Divide the power by 2
power = power / 2
# Multiply base to itself
base = (base * base) % MOD