Сайт о программировании, математике и моделировании
Архивы для Декабрь, 2010
Программа возведения в квадрат длинного числа
3 Декабрь
За операцию возведения в квадрат методом «треугольника» отвечает процедура SquareTri./ Вычисление квадрата длинного числа С = А2 методом «треугольника»
void SquareTri(
DIGIT C[ ], /* результат длины 2n цифр */
const DIGIT A[ ], /* основание длины n цифр */
int n) /* длина основания */ Читать дальше >
Сложение длинного числа
3 Декабрь
Приведем реализацию алгоритма сложения, а также ввод и вывод длинного числа на Паскале.
{основная программа}
Var A, B, C : Tlong;
Begin
Assign(Input, ‘Input.txt’); Reset(Input);
ReadLong(A); ReadLong(B) ;
Close(Input);
SumLongTwo(A, B, C); Читать дальше >
Сравнение «длинных» чисел длины n
3 Декабрь
Сравнение «длинных» чисел длины n цифр А==В */
int Cmp(
const DIGIT A[ ], /* первое число */
const DIGIT B[ ], /* второе число */
int n) /* длина чисел */
{
int i;
for(i=n-1; (i>=0)&&(A[i]==B[i]); i–);
if (i<0) return 0;
if(A[i]>B[i]) return +1;
return -1;
}
Сложение длинных чисел
3 Декабрь
За операцию сложения отвечает процедура ADD
DIGIT Аdd(
DIGIT C[ ], // результат
const DIGIT A[ ], // первое слагаемое
const DIGIT B[ ], // второе слагаемое
int n) // длина слагаемых Читать дальше >
Длинные числа. Вычисление обратного по модулю
3 Декабрь
При проверке ЭЦП необходимо вычислить величину v = (h(M1))q-2 (mod q). Это можно сделать, по крайней мере, двумя способами:
возведением в степень и вычислением обратного с помощью расширенного алгоритма Евклида. Действительно, в теории чисел известна малая теорема Ферма, которая утверждает, что если р — простое число, а – целое число, не делящееся на р, то ар-1 ≡ 1 (mod p). Читать дальше >
Возведение в степень в длинной арифметике
3 Декабрь
Обозначения.
Теперь мы будем решать задачу вычисления значения С = AB(mod P), где Р – простое число длины n цифр, А и С – числа меньшие Р, В – число длины s цифр.
Бинарный алгоритм возведения в степень
Известный всем из школы алгоритм возведения в степень В путем В-1 умножения очень неэффективен. При малых значениях В он еще приемлем, но при В порядка 2256 его сложность превышает всякие разумные пределы. Однако можно воспользоваться алгоритмом, который называется бинарным алгоритмом (иногда его называют схемой Горнера или дихотомическим алгоритмом). Читать дальше >
Модулярное умножение длинных чисел
3 Декабрь
Операцию умножения по модулю можно выполнять следующим образом. Если А и В < Р, то С = (А Ч В) (mod P) вычисляется так:
D:=A Ч B;
С := D mod P.
Аналогичным образом выполняется вычисление квадрата по модулю,
С = A2 (mod P) вычисляется так:
D := А2;
С := D mod P.
Вычисление остатка в длинной арифметике
3 Декабрь
Итак, теперь умеем умножать числа, но в алгоритмах ГОСТ Р 34.10-94 требуется уметь вычислять произведение двух чисел по модулю простого числа. Для его реализации необходимо произвести вычисление остатка от деления 2n-значного числа на n-значное. Эта операция называется редукцией по модулю. Выполнять ее можно двумя способами. Первый состоит в том, что необходимо выполнить процедуру деления и взять остаток. Второй метод носит имя П. Монтгомери, который предложил модифицировать саму операцию редукции. Что из этого получилось, рассмотрим далее. Читать дальше >
Возведение в квадрат длинного числа
3 Декабрь
Если немного заскочить вперед и посмотреть на любой из приведенных далее алгоритмов возведения в степень, то можно видеть, что одним из путей ускорения этой процедуры является ускорение работы алгоритма возведения во вторую степень. делать это можно, по крайней мере, тремя способами:
- умножать операнд на себя самого, используя при этом один из приведенных выше алгоритмов умножения,
- использовать модификацию метода Карацубы,
- воспользоваться методом «треугольника». Читать дальше >
Умножение длинных чисел
3 Декабрь
Умножение в столбик.
С умножением дело обстоит не так просто, как с операциями сложения и вычитания. Дело в том, что известный нам со школы алгоритм умножения “в столбик” не самый быстрый. Вот он.
Алгоритм 1.3. Умножение «в столбик» длинных чисел С = А*В Читать дальше >