Бимодульная модулярная арифметика — различия между версиями
Isaeva (обсуждение | вклад) |
Isaeva (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
Аддитивный характер вычислений в кольце вычетов <math> Z_p </math> порождает дополнительные расходы на выполнение арифметических операций. Это обусловлено тем, что результат выполненной операции может выйти за диапазон <math> Z_p </math>, тогда требуется корректировка результата, т.е. взятие результата выполненной операции по модулю. Мультипликативная операция над остатками x, y mod p более трудоемка, поэтому наиболее эффективным способом избежать прямой реализации мультипликативной операции является переход к индексам вычетов по основанию первообразного корня, однозначно связанных с данным модулярным кодом. | Аддитивный характер вычислений в кольце вычетов <math> Z_p </math> порождает дополнительные расходы на выполнение арифметических операций. Это обусловлено тем, что результат выполненной операции может выйти за диапазон <math> Z_p </math>, тогда требуется корректировка результата, т.е. взятие результата выполненной операции по модулю. Мультипликативная операция над остатками x, y mod p более трудоемка, поэтому наиболее эффективным способом избежать прямой реализации мультипликативной операции является переход к индексам вычетов по основанию первообразного корня, однозначно связанных с данным модулярным кодом. | ||
| + | |||
| + | В случае индексной арифметики операция «+» выполняется за один такт модульного суммирования, а операция «*» за такт модульного суммирования и два такта табличной операции. Для того, чтобы сбалансировать выполнение модульных операций Д.А. Поспелов ввел представление исходных операндов в виде пар <math> <|x|_p, ind_w|x|_p> </math>>, где <math> |x|_p </math> есть вычет <math> x </math> по модулю <math> p </math> , <math> i = ind_w|x|_p </math> - соответствующий вычету <math> |x|_p </math> индекс, при этом условно считается, что вычету 0 соответствует специальный символ λ, который обладает свойством λ+i=i+λ для любого для любого индекса <math> 0<=i<=p-2 </math> . Таким образом, все операции поля выполняются над парами: если требуется найти сумму двух операндов по модулю <math> p </math> , то суммируются по модулю <math> p </math> первые компоненты пар; для формирования второй компоненты пары результата этот результат преобразуется в индекс путем выборки значения из таблицы индексов (рис.1). Если требуется найти произведение двух операндов по модулю <math> p </math>, то суммируются по модулю <math> p - 1 </math> вторые компоненты пар; для формирования первой компоненты пары результата этот результат преобразуется в антилогарифм (вычет) путем выборки значения из таблицы вычетов (рис.2): | ||
| + | |||
= Кодовая конструкция проф. Д.А. Поспелова = | = Кодовая конструкция проф. Д.А. Поспелова = | ||
Версия 13:08, 28 мая 2014
Аддитивный характер вычислений в кольце вычетов 
порождает дополнительные расходы на выполнение арифметических операций. Это обусловлено тем, что результат выполненной операции может выйти за диапазон , тогда требуется корректировка результата, т.е. взятие результата выполненной операции по модулю. Мультипликативная операция над остатками x, y mod p более трудоемка, поэтому наиболее эффективным способом избежать прямой реализации мультипликативной операции является переход к индексам вычетов по основанию первообразного корня, однозначно связанных с данным модулярным кодом.
В случае индексной арифметики операция «+» выполняется за один такт модульного суммирования, а операция «*» за такт модульного суммирования и два такта табличной операции. Для того, чтобы сбалансировать выполнение модульных операций Д.А. Поспелов ввел представление исходных операндов в виде пар 
>, где 
есть вычет 
по модулю 
, 
- соответствующий вычету индекс, при этом условно считается, что вычету 0 соответствует специальный символ λ, который обладает свойством λ+i=i+λ для любого для любого индекса 
. Таким образом, все операции поля выполняются над парами: если требуется найти сумму двух операндов по модулю , то суммируются по модулю первые компоненты пар; для формирования второй компоненты пары результата этот результат преобразуется в индекс путем выборки значения из таблицы индексов (рис.1). Если требуется найти произведение двух операндов по модулю , то суммируются по модулю 
вторые компоненты пар; для формирования первой компоненты пары результата этот результат преобразуется в антилогарифм (вычет) путем выборки значения из таблицы вычетов (рис.2):
Кодовая конструкция проф. Д.А. Поспелова
