1 год назад - Нет комментариев
За операцию возведения в квадрат методом «треугольника» отвечает процедура SquareTri./ Вычисление квадрата длинного числа С = А2 методом «треугольника» void SquareTri( DIGIT C[ ], /* результат длины 2n цифр */ const DIGIT A[ ], /* основание длины n цифр */ int n) /* длина основания */ { TWODIGIT t,f; int i,j; Zero (С, 2*n); for
1 год назад - Нет комментариев
Приведем реализацию алгоритма сложения, а также ввод и вывод длинного числа на Паскале. {основная программа} Var A, B, C : Tlong; Begin Assign(Input, ‘Input.txt’); Reset(Input); ReadLong(A); ReadLong(B) ; Close(Input); SumLongTwo(A, B, C); Assign(Output, ‘Output.txt’); Rewrite(Output); WriteLong(C); Close(Output) End. {процедура ввода длинного числа} Procedure ReadLong(Var A : Tlong); Var ch : char; i : Integer; Begin
1 год назад - Нет комментариев
За операцию сложения отвечает процедура ADD DIGIT Аdd( DIGIT C[ ], // результат const DIGIT A[ ], // первое слагаемое const DIGIT B[ ], // второе слагаемое int n) // длина слагаемых { TWODIGIT T; DIGIT d=0; int i; for(i=0; i<n; i++) { T = (TWODIGIT)A[i]+B[i]+d; C[i] = LODIGIT(T); d = HIDIGIT(T); } return d;
1 год назад - Нет комментариев
При проверке ЭЦП необходимо вычислить величину v = (h(M1))q-2 (mod q). Это можно сделать, по крайней мере, двумя способами: возведением в степень и вычислением обратного с помощью расширенного алгоритма Евклида. Действительно, в теории чисел известна малая теорема Ферма, которая утверждает, что если р — простое число, а – целое число, не делящееся на р, то
1 год назад - 1 комментарий
Обозначения. Теперь мы будем решать задачу вычисления значения С = AB(mod P), где Р – простое число длины n цифр, А и С – числа меньшие Р, В – число длины s цифр. Бинарный алгоритм возведения в степень Известный всем из школы алгоритм возведения в степень В путем В-1 умножения очень неэффективен. При малых значениях
1 год назад - Нет комментариев
Операцию умножения по модулю можно выполнять следующим образом. Если А и В < Р, то С = (А Ч В) (mod P) вычисляется так: D:=A Ч B; С := D mod P. Аналогичным образом выполняется вычисление квадрата по модулю, С = A2 (mod P) вычисляется так: D := А2; С := D mod P. Операция
1 год назад - Нет комментариев
Итак, теперь умеем умножать числа, но в алгоритмах ГОСТ Р 34.10-94 требуется уметь вычислять произведение двух чисел по модулю простого числа. Для его реализации необходимо произвести вычисление остатка от деления 2n-значного числа на n-значное. Эта операция называется редукцией по модулю. Выполнять ее можно двумя способами. Первый состоит в том, что необходимо выполнить процедуру деления и
1 год назад - 1 комментарий
Если немного заскочить вперед и посмотреть на любой из приведенных далее алгоритмов возведения в степень, то можно видеть, что одним из путей ускорения этой процедуры является ускорение работы алгоритма возведения во вторую степень. делать это можно, по крайней мере, тремя способами: умножать операнд на себя самого, используя при этом один из приведенных выше алгоритмов умножения,
1 год назад - 1 комментарий
Умножение в столбик. С умножением дело обстоит не так просто, как с операциями сложения и вычитания. Дело в том, что известный нам со школы алгоритм умножения “в столбик” не самый быстрый. Вот он. Алгоритм 1.3. Умножение «в столбик» длинных чисел С = А*В длины n цифр 1. C := 0; (достаточно обнулить n младших цифр)
1 год назад - Нет комментариев
Складывать и вычитать учат с первого класса школы. И в отличие от умножения ничего более эффективного, чем “первоклассный” школьный алгоритм “в столбик” и не надо придумывать.. Итак, ниже приведен алгоритм вычисления суммы С =А + В чисел А и В длины n цифр. При этом помимо n – значного результата С возвращается также бит переноса
