logo search
Коды и шифры

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

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

2k<n<2k+1;

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

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

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