Прежде всего, введем обозначение. Обозначим через m длину в байтах машинного слова, которое используется в качестве минимального элемента памяти. Конкретный выбор зависит от того, какой максимальный длинны элемент данных можно умножать без потери разрядов. Для процессоров Intel начиная с модели 80386 – m=32. Для процессора Digital Alpha можно использовать m=64.

В языке Си удобно представлять в виде переменных типа unsigned short. Для m=32 можно использовать unsigned long. В случае m=64 единообразия пока нет. Некоторые компиляторы поддерживают тип данных unsigned long long, другие unsigned longlong, в Microsoft Visual C++ и Borland Builder можно использовать unsigned _int64. В любом случае везде далее в текстах программ будем использовать тип с именем DIGIT для обозначения беззнакового типа данных длинны m битов, а m – как символьную константу с подходящим значением.

Будем хранить длинные числа, с которыми работает программа, в массивах m-разрядных слов. Опишем, каким образом произвольное неотрицательное целое число X превращается в последовательность m-разрядных слов. Фиксируем в качестве основания системы счисления число b=2m. Как известно, любое неотрицаельное целое число X<b m можно разложить по степеням b:                                                      n-1

X = ∑Xibi,

i=0

где Xi – некоторые неотрицательные целые числа меньшие b. Число X сохраняется в памяти компьютера как массив m-битовых слов с элементами X[i] = Xi. Числа Xi называются цифрами числа X, а число X называется n-значным длинным числом.

Таким образом, число X представляется в программе, как массив.

DIGIT X[n];   /* n – константа*/

Помимо базового типа DIGIT нам также понадобится тип данных в 2 раза длиннее (то есть беззнаковое целое длинны 2m бит). Назовем его TWODIGIT. Он пригодится при реализации арифметических операций для того, чтобы не терять старшие биты результата.

Для 2m-битного числа Т обозначим LODIGIT(T) число типа DIGIT, состоящее из младших m разрядов, а HIDIGIT(T) – число типа DIGIT, состоящее из младших m разрядов числа T. На языке Си это реализуется двумя макроопределениями:

#define LODIGIT(T) ((DIGIT)(T))

#define HIDIGIT(T) ((DIGIT)((T)>>m))

И наоборот, для двух m-битных чисел А и В обозначим MAKELONG(A,B) 2m-битное число, чьи младшие биты совпадают с числом А, а старшие – с числом В. Соответствующий макрос:

#define MAKELONG(A,B) ((A)|((TWODIGIT)(B)<<m))

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

Функции Assign и AssignDigit выполняют операции присвоения A:=B и A:=x, соответственно, где А и В – n-значные длинные числа, x – цифра:

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

В программе на языке Си, соответственно, программистом должна быть точно определена константа MAX_SIZE.

В случае рассматриваемого ГОСТ Р 34.10-94

MAX_SIZE*m = 512 или 1024.

При необходимости реализовать функции, не зависящие от такого ограничения, придется выделять память для временных массивов динамически, что не всегда эффективно.