Функция Double-and-add

ГЛАВА 2. ОСНОВНЫЕ ПОНЯТИЯ
10
Формально положительный модуль здесь определен для c = a (mod b) как a = bx + c, где 0 c < b
и x - целое число со знаком, которое отбрасывается (b - положительное ненулевое целое число).
Обратите внимание, что, если a S n, -a (mod n) совпадает с n - a.
2.2.1 Модульное сложение и умножение
В информатике важно избегать больших чисел при выполнении модульной арифметики.
Например, если у нас есть 29 + 87 (mod 99) и нам не разрешены переменные с тремя или более цифрами
(например, 116 = 29 + 87), то мы не можем вычислить 116 (mod 99) = 17 напрямую.
Чтобы выполнить c = a + b (mod n), где a и b каждый меньше модуля n, мы можем сделать это:
• Вычислите x = n - a. Если x > b, то c = a + b, в противном случае c = b - x.
Мы можем использовать модульное сложение для достижения модульного умножения (a * b (mod n) = c) с
помощью алгоритма, называемого "удвоение и сложение". Давайте продемонстрируем это на примере. Допустим, мы хотим сделать 7 + 8
(mod 9) = 2. Это то же самое, что
7+ 8 = 8 + 8 + 8 + 8 + 8 + 8 + 8 ( мод 9)
Теперь разбейте это на группы по две.
(8 (8 + (8 + 8
И снова группами по два человека.
[(8 + + (8 + ] + (8 + + 8
Общее количество операций с + точками уменьшается с 6 до 4, потому что нам нужно найти (8 + только один раз.
Функция Double-and-add реализуется путем преобразования первого числа ('multiplicand' a) в двоичное
(в нашем примере 7 -> [0111]), затем перебора двоичного массива и удвоения и сложения.
Давайте создадим массив A = [0111] и проиндексируем его 3,2,1,0.1 A[0] = 1 - это первый элемент A и
наименее значимый бит. Мы устанавливаем переменную результата изначально равной r = 0, а переменную суммы -
изначально равной s = 8 (в более общем случае мы начинаем с s = b). Мы следуем этому алгоритму:
1. Повторите: i = (0, ..., Asize - 1)
(a) Если A[i] == 1, то r = r | s (mod n).
(b) Вычислите s = + s (mod n).
2. Используйте конечное значение r: c = r.
Эффект удвоения и добавления становится очевидным при больших количествах. Например, для прямого
сложения 215 230 потребуется около 215 + операций, в то время как для двойного сложения требуется всего 15!
Это известно как нумерация 'LSB 0', поскольку младший значащий бит имеет индекс 0. Мы будем использовать 'LSB 0' для остальной
части этой главы. Дело здесь в ясности, а не в точных условностях.