Бимодульная модулярная арифметика

Материал из Модулярная арифметики
Перейти к: навигация, поиск

Аддитивный характер вычислений в кольце вычетов  Z_p порождает дополнительные расходы на выполнение арифметических операций. Это обусловлено тем, что результат выполненной операции может выйти за диапазон  Z_p , тогда требуется корректировка результата, т.е. взятие результата выполненной операции по модулю. Мультипликативная операция над остатками x, y mod p более трудоемка, поэтому наиболее эффективным способом избежать прямой реализации мультипликативной операции является переход к индексам вычетов по основанию первообразного корня, однозначно связанных с данным модулярным кодом.

В случае индексной арифметики операция «+» выполняется за один такт модульного суммирования, а операция «*» за такт модульного суммирования и два такта табличной операции. Для того, чтобы сбалансировать выполнение модульных операций Д.А. Поспелов ввел представление исходных операндов в виде пар   <|x|_p, ind_w|x|_p> >, где  |x|_p есть вычет  x по модулю  p ,   i = ind_w|x|_p - соответствующий вычету  |x|_p индекс, при этом условно считается, что вычету 0 соответствует специальный символ λ, который обладает свойством λ+i=i+λ для любого для любого индекса  0<=i<=p-2 . Таким образом, все операции поля выполняются над парами: если требуется найти сумму двух операндов по модулю  p , то суммируются по модулю  p первые компоненты пар; для формирования второй компоненты пары результата этот результат преобразуется в индекс путем выборки значения из таблицы индексов (рис.1). Если требуется найти произведение двух операндов по модулю  p , то суммируются по модулю  p - 1 вторые компоненты пар; для формирования первой компоненты пары результата этот результат преобразуется в антилогарифм (вычет) путем выборки значения из таблицы вычетов (рис.2):


Кодовая конструкция проф. Д.А. Поспелова

Рис.1. Структурная схема операции сложения
Рис.2. Структурная схема операции умножения

Модифицированная кодовая конструкция