9. Арифметические операции над большими числами

1. Арифметические операции над большими числами

2.

Диапазон чисел, которые используются в реальных задачах
криптографии, доходит до нескольких сот и даже тысячи
десятичных цифр. Такой диапазон чисел не соответствует базовым
типам данных современных компьютеров. Число, которое состоит
из несколько сот (и даже тысяч) десятичных знаков, нельзя записать
как единый объект ни в одно базовое устройство компьютера.
Поэтому компьютерное представление таких чисел и операции
над ними приходится реализовывать самостоятельно в виде
некоторых программ

3.

Числа записаны в двоичной системе счисления, где b —
фиксированное натуральное число, b ≥ 2. При этом
натуральное число, записываемое не более чем n цифрами
двоичной системе счисления, мы обозначаем u1 … un.

4. Алгоритм сложения неотрицательных целых чисел

Для двух неотрицательных чисел u1 … un и v1 … vn вычисляется их сумма
w0… wn; при этом w0 — цифра переноса — всегда равна 0 или 1.
Шаг 1. Присвоить j = n, k = 0 (здесь j идет по разрядам, k следит
за переносом).
Шаг 2. Присвоить wj = uj + vj + k (mod b), wj — наименьший
неотрицательный вычет в данном классе вычетов;