Проведение операции модульного возведения в степень путем последовательного умножения числа А самого на себя, применяющейся для зашифрования/расшифрования в RSA, требует большого объема памяти для хранения полученных чисел и времени. Для решения этой проблемы существует метод последовательного возведения в квадрат, с помощью которого можно добиться, чтобы не возникали числа, большие А2, и при этом существенно возросла скорость возведения в степень. Суть его состоит в следующем:

1. В представляется в двоичном виде:

к

В = ?х(2', где Xi = 0 + 1 и к = [log2B] + 1.

i=0

2. Затем вычисляются числа вида (A2 mod n, где i - 0 -г к); данные вычисления требуют к возведений в квадрат.

3. Далее числа A2 mod n последовательно перемножаются с одновременным сведением по mod n; этих операций будет не более к - 1.

представлениями чисел в машине. Так, при употреблении двоичного представления числа используется на 20% меньше памяти, нежели при двоично-десятичном представлении.

Рис. 1.15 Алгоритм модулярного умножения A x В mod n
Таким образом, получаем не более 2к - 1 операций модулярного умно-жения с числами, меньшими п. Данный метод разрешается модернизировать за счет сокращения числа ненулевых х{ в битовом представлении В: В = ЪпХп + IviA"'1 + ... + btX + Ь0, где bn ^ 0,0 < bj < Я, i = 0 ^- п. Выбор основания X производится в соответствии с представлениями чисел в машине. Так, при употреблении двоичного представления числа используется на 20% меньше памяти, нежели при двоично-десятичном представлении.