Как возведение в степень путем возведения в квадрат быстрее?

Question

Предположим, вы хотите высчитать 5^65537 вместо умножения 565537 раз, рекомендуется делать ((5^2)^16)*5. Это приводит к 16-кратному возведению в квадрат и одному умножению.
Но мой вопрос заключается в том, что вы не компенсируете число квадратов, возводя квадраты очень больших чисел? как это происходит быстрее, когда вы переходите к базовому умножению бит в компьютерах.
После прочтения комментариев, у меня это сомнение:

 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, чтобы избежать массивных промежуточных чисел.