М26. Эффективность возведения в степень методом последовательного возведения в квадрат

Если задано число X, которое мы хотим возвести в n-ю степень, то мы могли бы вычислить Xⁿ, просто умножив X на себя n-1 раз. Если n невелико, то так и следует поступить, но в случае большого n этот способ неэффективен. Пусть число k таково, что

2^k<n<2^k+1;

тогда k=[log₂n], где [z] обозначает, как принято в математике, целую часть числа z.

При вычислении значений X², X⁴, X⁸,... методом последовательного возведения в квадрат для возведения числа в степень 2^k необходимо выполнить k операций возведения в квадрат, то есть k умножений. Двоичное представление числа n содержит не более (k+1) единицы, поэтому для вычисления величины Xⁿ надо перемножить между собой не более k+1 чисел из множества X, X², X⁴,... . Это означает, что понадобится выполнить не более k дополнительных операций. В итоге получаем, что общее число умножений не превосходит 2k.

Поскольку k<(log₂n+1), то отсюда следует, что для вычисления Xⁿ методом последовательного возведения в квадрат требуется не более 2(log₂n+1) умножений, в то время как при вычислении "в лоб" их потребуется n-1. Для малых значений n разница не так уж велика. Например, для n=7 при вычислении "в лоб" нужно 6 умножений, а для метода последовательного возведения в квадрат их потребуется 4. Однако с ростом n разница очень быстро становится существенной. Например, для n=127 для вычислений "в лоб" нужно выполнить 126 умножений, а при последовательном возведении в квадрат - только 12. Для действительно больших значений порядков, которые чаще всего и применяются в методе зашифрования-расшифрования RSA, вместо астрономического числа умножений нужно выполнить всего несколько сотен.