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

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

Система остаточных классов (СОК) (от англ. Residue number system, другое название Модулярная арифметика) — непозиционная система счисления. Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором взаимно простых модулей , называемых базисом, с произведением так, что каждому целому числу из отрезка ставится в соответствие набор вычетов , где

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

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

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

Формула для сложения: , где

Аналогично выполняются вычитание, умножение и деление. Замечание: на деление накладываются дополнительные ограничения. Деление должно быть целочисленным, то есть делитель должен нацело делить делимое. Делитель должен быть взаимопростым со всеми модулями базиса.

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

  • Возможность представления только ограниченного количества чисел.
  • Отсутствие эффективных алгоритмов для сравнения чисел, представленных в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям .
  • Медленные и требующие работы с большими числами реализации алгоритмов перевода из позиционной системы счисления в СОК и обратно.
  • Сложные алгоритмы деления (для случая, когда результат не является целым)
  • Трудность в обнаружении переполнения

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

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

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

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

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

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

Рассмотрим СОК с базисом . В этом базисе можно взаимооднозначно представить числа из промежутка от до , так как . Таблица соответствия чисел из позиционной системы счисления и системы остаточных классов:

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

Сложим два числа 9 и 14 в базисе . Их представление в заданном базисе и (см. табличку выше). Воспользуемся формулой для сложения:

 — по таблице убеждаемся, что результат равен 23.

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

Умножим два числа 4 и 5 в базисе . Их представление в заданном базисе и (см. табличку выше). Воспользуемся формулой для умножения:

 — по таблице убеждаемся, что результат равен 20.

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

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

Деление может быть выполнено аналогично умножению, но только если делитель делит делимое нацело, без остатка.
Для модулей разделим число 1872 на 9.
Делим на .

Воспользуемся формулой


Здесь надо сказать, что , что не то же самое, что просто разделить x на y.
По формуле получаем







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

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

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

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

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

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

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