Сложение длинных чисел

При проверке ЭЦП необходимо вычислить величину v = (h(M1))q-2 (mod q). Это можно сделать, по крайней мере, двумя способами: возведением в степень и вычислением обратного с помощью расширенного алгоритма Евклида. Действительно, в теории чисел известна малая теорема Ферма, которая ут­верждает, что если р — простое число, а – целое число, не делящееся на р, то

Операцию умножения по модулю можно выполнять следующим образом. Если А и В < Р, то С = (А Ч В) (mod P) вычисляется так: D:=A Ч B; С := D mod P. Аналогичным образом выполняется вычисление квадрата по модулю, С = A2 (mod P) вычисляется так: D := А2; С := D mod P. Операция

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

Складывать и вычитать учат с первого класса школы. И в отличие от умножения ничего более эффективного, чем “первоклассный” школьный алгоритм “в столбик” и не надо придумывать.. Итак, ниже приведен алгоритм вычисления суммы С =А + В чисел А и В длины n цифр. При этом помимо n – значного результата С возвращается также бит переноса