Система остаточных классов

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Система остаточных классов (СОК) (от англ. Residue number system, другое название Модулярная арифметика) — непозиционная система счисления. Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором взаимно простых модулей (m_1, m_2, \dots, m_n), называемых базисом, с произведением M=m_1\cdot m_2\cdot \dots\cdot m_n так, что каждому целому числу x из отрезка [0,M-1] ставится в соответствие набор вычетов (x_1, x_2, \dots, x_n), где

x_1 \equiv x \pmod{m_1};
x_2 \equiv x \pmod{m_2};
x_n \equiv x \pmod{m_n}.

При этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка [0,M-1].

Преимущества системы остаточных классов[править | править вики-текст]

  • В СОК арифметические операции (сложение, вычитание, умножение, деление) выполняются покомпонентно, если про результат известно, что он является целочисленным и также лежит в [0,M-1].

Формула для сложения: (x_1, x_2, \dots, x_n) + (y_1, y_2, \dots, y_n) = (z_1, z_2, \dots, z_n), где

z_1 \equiv (x_1 + y_1) \pmod{m_1};
z_2 \equiv (x_2 + y_2) \pmod{m_2};
z_n \equiv (x_n + y_n) \pmod{m_n};

Аналогично выполняются вычитание, умножение и деление.

Недостатки системы остаточных классов[править | править вики-текст]

  • Возможность представления только ограниченного количества чисел.
  • Отсутствие эффективных алгоритмов для сравнения чисел, представленных в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям (m_1, m_1\cdot m_2, \dots, m_1\cdot m_2\cdot\dots\cdot m_{n-1}).
  • Медленные и требующие работы с большими числами реализации алгоритмов перевода из позиционной системы счисления в СОК и обратно.
  • Сложные алгоритмы деления (для случая, когда результат не является целым)
  • Трудность в обнаружении переполнения

Применение системы остаточных классов[править | править вики-текст]

СОК широко используется в микроэлектронике в специализированных устройствах ЦОС, где требуется:

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

Специальные системы модулей[править | править вики-текст]

В модулярной арифметике существуют специальные наборы модулей, которые позволяют частично нивелировать недостатки и для которых существуют эффективные алгоритмы сравнения чисел и для прямого и обратного перевода модулярных чисел в позиционную систему счисления. Одной из самых популярных систем модулей является набор из трех взаимнопростых чисел вида {2n−1, 2n, 2n+1}[1]

Пример[править | править вики-текст]

Рассмотрим СОК с базисом (2;3;5). В этом базисе можно взаимооднозначно представить числа из промежутка от 0 до 29, так как M = 2\times 3\times 5 = 30. Таблица соответствия чисел из позиционной системы счисления и системы остаточных классов:

0=(0;0;0) 1=(1;1;1) 2=(0;2;2) 3=(1;0;3) 4=(0;1;4)
5=(1;2;0) 6=(0;0;1) 7=(1;1;2) 8=(0;2;3) 9=(1;0;4)
10=(0;1;0) 11=(1;2;1) 12=(0;0;2) 13=(1;1;3) 14=(0;2;4)
15=(1;0;0) 16=(0;1;1) 17=(1;2;2) 18=(0;0;3) 19=(1;1;4)
20=(0;2;0) 21=(1;0;1) 22=(0;1;2) 23=(1;2;3) 24=(0;0;4)
25=(1;1;0) 26=(0;2;1) 27=(1;0;2) 28=(0;1;3) 29=(1;2;4)

Пример сложения[править | править вики-текст]

Сложим два числа 9 и 14 в базисе (2;3;5). Их представление в заданном базисе 9=(1;0;4) и 14=(0;2;4) (см. табличку выше). Воспользуемся формулой для сложения: (z_1, z_2, z_3) = (1, 0, 4) + (0, 2, 4)

z_1 \equiv (x_1 + y_1) \pmod{m_1} \equiv (1 + 0) \pmod{2} = 1;
z_2 \equiv (x_2 + y_2) \pmod{m_2} \equiv (0 + 2) \pmod{3} = 2;
z_3 \equiv (x_3 + y_3) \pmod{m_3} \equiv (4 + 4) \pmod{5} = 3;

(z_1, z_2, z_3) = (1, 2, 3) — по таблице убеждаемся, что результат равен 23.

Пример умножения[править | править вики-текст]

Умножим два числа 4 и 5 в базисе (2;3;5). Их представление в заданном базисе 4=(0;1;4) и 5=(1;2;0) (см. табличку выше). Воспользуемся формулой для умножения: (z_1, z_2, z_3) = (0, 1, 4) * (1, 2, 0)

z_1 \equiv (x_1 * y_1) \pmod{m_1} \equiv (0 * 1) \pmod{2} = 0;
z_2 \equiv (x_2 * y_2) \pmod{m_2} \equiv (1 * 2) \pmod{3} = 2;
z_3 \equiv (x_3 * y_3) \pmod{m_3} \equiv (4 * 0) \pmod{5} = 0;

(z_1, z_2, z_3) = (0, 2, 0) — по таблице убеждаемся, что результат равен 20.

Замечание: если бы мы умножали или складывали числа, которые дали в результате умножения число больше или равное M = 30, то полученный результат RES \equiv REAL \pmod{M}, где REAL — результат операции в позиционной системе счисления.

Пример деления, при условии, что оно делится нацело[править | править вики-текст]

Деление может быть выполнено аналогично умножению, но только если делитель делит делимое нацело, без остатка.
Для модулей (29;31;32) разделим число 1872 на 9.
Делим 1872=(16;12;16) на 9=(9;9;9).

Воспользуемся формулой
z_i \equiv (x_i * y_i^{-1}) \pmod{m_i};

Здесь надо сказать, что y_i^{-1}*y_i=1 \pmod{m_i}, что не то же самое, что просто разделить x на y.
По формуле y_i^{m_i-1}=1 \pmod{m_i} получаем
9^{29-2} \pmod{29} = 13
9^{31-2} \pmod{31} = 7
9^{32-2} \pmod{32} = 17


z_1 \equiv (16*13) \pmod{29} = 5
z_2 \equiv (12*7) \pmod{31} = 22
z_3 \equiv (16*17) \pmod{32} = 16

Это и есть правильный результат — число 208. Однако такой результат можно получить только если известно, что деление производится без остатка.

См. также[править | править вики-текст]

Сравнение по модулю

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

  • Книга «Residue Number Systems: Theory and Implementation», Amos Omondi, Benjamin Premkumar — наиболее исчерпывающая информация о применении СОК с подробными примерами (на английском языке).
  • Червяков Н. И., Евдокимов А. А., Галушкин А. И., Лавриненко И. Н. и др. Применение искусственных нейронных сетей и системы остаточных классов в криптографии — М.: ФИЗМАТЛИТ, 2012.- 280 c. — ISBN 978-5-9221-1386-1.

Ссылки[править | править вики-текст]