Реализация методами объектно-ориентированного программирования сверхдлинной целочисленной арифметики

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

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

Представление целого числа а в системе счисления с основанием В имеет вид

а = an -1 Bn -1 + an -2 Bn -2 +…+ a 1 B + а 0,

где 0 ≤ аi < B.

Данное представление целого числа аналогично представлению полинома степени n - 1:

а (x) = an -1 xn -1 + an -2 xn -2 +…+ a 1 x + а 0

с коэффициентами ai, 0 ≤ ai < B.

Замечание. Знак числа, как и место десятичной точки, можно запомнить в отдельной переменной и учитывать при выполнении операций.

Сверхдлинное целое число хранится в виде массива цифр. Цифры используются из системы счисления. Применяется десятичная система счисления и её степени (десять тысяч, миллиард), либо двоичная система счисления.

Операции над числами длинной арифметики производятся с помощью "школьных" алгоритмов сложения, вычитания, умножения, деления столбиком, или алгоритмов быстрого умножения: быстрое преобразование Фурье и алгоритм Карацубы.

Для поддержки отрицательных чисел вводится дополнительный флаг "отрицательности" числа или дополняющие коды.

Сформулируем основные алгоритмы для выполнения арифметических операций с большими целыми числами.

Не нашли, что искали? Воспользуйтесь поиском: