exponentiation - 通过平方取幂如何更快？

Question

假设你想计算5^65537而不是乘数5 65537，建议这样做((5^2)^16)*5。这导致 16 次平方和 1 次乘法。
但我的问题是你不是通过平方非常大的数字来补偿平方的次数吗？当您深入到计算机中的基本位乘法时，这如何更快。
看完评论，我有这样的疑问：

     How is the cost of each multiplication not dependant on the size. because when
multiplying the number of bits of the multiplier will increase and this will increase the 
number of additions and the number of left shifts.

Answer 1

计算乘法运算：

5^65537 = 65537 multiplications
((5^2)^16)*5 = (2 + 16 + 1) = 19 multiplications.

从中可以看出，尽管乘法对更大的数字起作用，但工作量要少得多。该算法称为平方和乘法。

在实践中，需要像这样计算大量数字的密码系统使用一种称为模幂的技术来避免大量中间数字。