为什么正常的重复乘幂算法效率不高？
Why normal repeated multiplication of power algorithm is not efficient?
作为问题，我不明白为什么我们需要一些算法，如指数平方或模幂来计算数字的幂。
例如，我有一个像这样的重复乘法算法：
def expt_mul(a, n):
r = 1
for i in xrange(n):
r *= a
return r
a自乘n次，所以复杂度为O(n)，为什么效率不高？
有些算法需要对数字进行非常大的幂运算。特别是来自密码学的算法浮现在脑海中，例如 Diffie-Hellman key exchange.
虽然您的算法可能适用于大多数日常任务，但当您处理非常大的指数时，使用它就变得不可行，因此改用平方取幂。
why we need some algorithm like exponential by squaring or modular exponentiation for calculating the power of a number.
请注意，平方求幂与模幂求幂的效果不同。第一个是将实体提升到某个整数次方的有效算法，而后者是计算 (a^b) modulo c 形式表达式的方法，其中用于求幂的算法不是特别相关。
例如，在加密中，通常会进行取幂，其中指数可以达到 2100 或更多。假设您每秒可以进行 1010 次乘法运算，那么您所说的就是需要大约 1020 秒的时间。这样表达，你可能会耸耸肩说 "so what?"，所以让我们将其转换为年：1020 秒 / 3600 sec/hour / 24 hr/day / 365.25 days/year / 14E9 years/current 宇宙年龄 => 超过当前宇宙年龄的 226 倍！将其与对数时间算法进行对比，后者将在数百次操作中执行 2100 次幂运算——从您的角度来看几乎是瞬间完成的。
作为问题，我不明白为什么我们需要一些算法，如指数平方或模幂来计算数字的幂。
例如，我有一个像这样的重复乘法算法：
def expt_mul(a, n):
r = 1
for i in xrange(n):
r *= a
return r
a自乘n次，所以复杂度为O(n)，为什么效率不高？
有些算法需要对数字进行非常大的幂运算。特别是来自密码学的算法浮现在脑海中，例如 Diffie-Hellman key exchange.
虽然您的算法可能适用于大多数日常任务，但当您处理非常大的指数时，使用它就变得不可行，因此改用平方取幂。
why we need some algorithm like exponential by squaring or modular exponentiation for calculating the power of a number.
请注意，平方求幂与模幂求幂的效果不同。第一个是将实体提升到某个整数次方的有效算法，而后者是计算 (a^b) modulo c 形式表达式的方法，其中用于求幂的算法不是特别相关。
例如，在加密中，通常会进行取幂，其中指数可以达到 2100 或更多。假设您每秒可以进行 1010 次乘法运算，那么您所说的就是需要大约 1020 秒的时间。这样表达，你可能会耸耸肩说 "so what?"，所以让我们将其转换为年：1020 秒 / 3600 sec/hour / 24 hr/day / 365.25 days/year / 14E9 years/current 宇宙年龄 => 超过当前宇宙年龄的 226 倍！将其与对数时间算法进行对比，后者将在数百次操作中执行 2100 次幂运算——从您的角度来看几乎是瞬间完成的。