Вычисление степеней, возведение сравнений в степень

 

Многие результаты теории сравнений связаны с остатками высоких степеней чисел, поэтому обсудим интересную задачу эффективного вычисления xⁿ по заданным x и n, где n – положительное целое число. Пусть, например, нам предложили вычислить x¹⁶; мы могли бы просто начать с x и умножить его на себя последовательно 15 раз. Однако тот же ответ можно получить всего за четыре умножения, если последовательно вычислить x², x⁴, x⁸, x¹⁶, возводя в квадрат каждый из промежуточных результатов.

Та же идея применима, вообще говоря, при произвольном значении n. А именно, запишем n в двоичной системе счисления и заменим в этой записи каждую цифру “1” парой букв SX, а каждую цифру “0” – буквой S, после чего вычеркнем крайнюю левую пару букв SX. Результат[3] превращается в правило вычисления , если букву “S” интерпретировать как операцию возведения в квадрат, а букву “X” – как операцию умножения на x. Например, если n = 23, то его двоичным представлением будет 10111; строим последовательность SX S SX SX SX, удаляем из нее начальную пару SX и в итоге получаем следующее правило ычисления: S SX SX SX. Согласно этому правилу мы должны возвести x в квадрат, затем снова возвести в квадрат, затем умножить на x, возвести в квадрат, умножить на x, возвести в квадрат и, наконец, умножить на x”; при этом мы последовательно вычисляем x², x⁴, x⁵, x¹⁰, x¹¹, x²², x²³.

Этот бинарный метод очень древний; он появился раньше 200 г. до н. э. в Древней Индии; однако в течение последующих 2000 лет этот метод,по-видимому, больше ни разу не упоминался!

Бинарный метод “S и X” вычисления xⁿ не требует никакой дополнительной оперативной рабочей памяти, за исключением памяти для хранения значения x и текущего промежуточного результата, поэтому такой метод удобен для схемной реализации на двоичной машине. Его можно также без труда запрограммировать как для двоичной, так и для десятичной машины; но при его реализации необходимо считывать двоичное представление числа n слева направо, в то время как обычно такое считывание удобно производить справа налево. Используя, например, двоичную ЭВМ, мы можем сдвигать последовательно двоичное представление числа n вправо на один бит, пока в результате не получим нуль; работая с десятичной ЭВМ, мы можем делить на 2 (или, что то же, умножать на 5 или на ), чтобы вызвать сдвиг двоичного представления справа налево. Вот почему часто более удобен следующий алгоритм, основанный на прочтении числа справа налево.

Алгоритм. (Бинарный метод возведения в степень, основанный на считывании справа налево.) При помощи этого алгоритма вычисляется xⁿ, где n – положительное число. (Здесь x принадлежит произвольной алгебраической системе, в которой определена ассоциативная операция умножения с единичным элементом 1.)

1. [Начальная установка.] Установить N ¬ n, Y ¬ 1, Z ¬ x.

2. [Разделить N пополам.] (В этот момент выполняется соотношение xⁿ = Y·Z^N.) Установить и одновременно определить, было ли старое значение N четно или нечетно. Если N было четным, перейти к выполнению шага 5.

3. [Умножить Y на Z.] Установить Y ¬ Y * Z.

4. [N = 0?] Если N = 0, то выполнение алгоритма закончено; ответ равен Y.

5. [Возвести Z в квадрат.] Установить Z ¬ Z * Z и вернуться в шаг 2.

Число умножений, необходимых для выполнения алгоритма, равно ëlog₂ nû + j(n), где j (n) – число единиц в двоичном представлении числа n. Это на одно умножение больше, чем в бинарном методе, основанном на считывании “слева направо”, о котором шла речь в начале пункта, вследствие того факта, что первое выполнение шага 3 состоит просто-напросто в умножении на 1.

Предположим вновь, что имеется сравнение

a º b (mod m).

Как мы только, что выдели можно умножить это сравнение на себя, получив

a² º b² (mod m).

Вообще можно, умножив это сравнение на себя нужное количество раз, получить

aⁿ º bⁿ (mod m)

для любого целого положительного числа n.

Многие результаты теории сравнений связаны с остатками высоких степеней чисел, поэтому покажем, как можно продолжить процесс возведения в степень. Предположим, например, что мы хотим найти остаток сравнения

3⁸⁹ (mod 7).

Одним из путей для выполнения этого является повторное возведеие в квадрат. Для возведения в степень воспользуемся вышеприведенным алгоритмом. Запишем показатель степени в двоичной системе счисления: 89₁₀ = 1011001₂. Поэтому, правило вычисления будет следующим: S SX SX S S SX. Последовательно находим:

3 º 3 (mod 7),

3² º 9 º 2 (mod 7),

3⁴ º 4 (mod 7),

3⁵ º 12 º 5 (mod 7),

3¹⁰ º 25 º 4 (mod 7),

3¹¹ º 12 º 5 (mod 7),

3²² º 25 º 4 (mod 7),

3⁴⁴ º 16 º 2 (mod 7),

3⁸⁸ º 4 (mod 7),

3⁸⁹ º 12 º 5 (mod 7).

Таким образом, 3⁸⁹ mod 7 = 5.