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.

从中可以看出，尽管乘法适用于更大的数字，但工作量要少得多。该算法名为 Square and Multiply.

实际上，需要像这样计算大量数字的密码系统使用一种称为 Modular Exponentiation 的技术。避免大量中间数。