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

Система остаточных классов (СОК) (англ. residue number system) — система счисления, основанная на модулярной арифметике.

Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором попарно взаимно простых модулей [math]\displaystyle{ (m_1,\, m_2,\, \dots,\, m_n) }[/math], то есть таких, что [math]\displaystyle{ \gcd(m_i,\, m_j)=1 }[/math] [math]\displaystyle{ (i,\, j=0,\, 1,\, \dots,\, n;\ i\neq j) }[/math], называемых базисом, и произведением [math]\displaystyle{ M=m_1\cdot m_2\cdot \ldots \cdot m_n, }[/math] так, что каждому целому числу [math]\displaystyle{ x }[/math] из отрезка [math]\displaystyle{ [0,\ M-1] }[/math] ставится в соответствие набор вычетов [math]\displaystyle{ (x_1,\, x_2,\, \dots,\, x_n) }[/math], где

[math]\displaystyle{ x_1 \equiv x \pmod{m_1}; }[/math]

[math]\displaystyle{ x_2 \equiv x \pmod{m_2}; }[/math]

[math]\displaystyle{ \dots\dots\dots\dots\dots\dots\dots }[/math]

[math]\displaystyle{ x_n \equiv x \pmod{m_n}. }[/math]

При этом китайская теорема об остатках гарантирует однозначность (единственность) представления целых неотрицательных чисел из отрезка [math]\displaystyle{ [0,\ M-1] }[/math].

Преимущества системы остаточных классов

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

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

[math]\displaystyle{ z_1 \equiv (x_1 + y_1) \pmod{m_1}; }[/math]

[math]\displaystyle{ z_2 \equiv (x_2 + y_2) \pmod{m_2}; }[/math]

[math]\displaystyle{ \dots\dots\dots\dots\dots\dots\dots\dots\dots }[/math]

[math]\displaystyle{ z_n \equiv (x_n + y_n) \pmod{m_n}. }[/math]

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

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

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

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

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

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

Практическое применение: чехословацкая ламповая ЭВМ «EPOS», советская военная многопроцессорная суперЭВМ 5Э53, предназначенная для решения задач противоракетной обороны.

Специальные системы модулей

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

Пример

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

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

Пример сложения

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

[math]\displaystyle{ z_1 \equiv (x_1 + y_1) \pmod{m_1} \equiv (1 + 0) \pmod{2} = 1; }[/math]

[math]\displaystyle{ z_2 \equiv (x_2 + y_2) \pmod{m_2} \equiv (0 + 2) \pmod{3} = 2; }[/math]

[math]\displaystyle{ z_3 \equiv (x_3 + y_3) \pmod{m_3} \equiv (4 + 4) \pmod{5} = 3; }[/math]

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

Пример умножения

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

[math]\displaystyle{ z_1 \equiv (x_1 * y_1) \pmod{m_1} \equiv (0 * 1) \pmod{2} = 0; }[/math]

[math]\displaystyle{ z_2 \equiv (x_2 * y_2) \pmod{m_2} \equiv (1 * 2) \pmod{3} = 2; }[/math]

[math]\displaystyle{ z_3 \equiv (x_3 * y_3) \pmod{m_3} \equiv (4 * 0) \pmod{5} = 0; }[/math]

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

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

Пример деления, при условии, что возможно деление нацело

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

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

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

[math]\displaystyle{ z_1 \equiv (16*13) \pmod{29} = 5, }[/math]
[math]\displaystyle{ z_2 \equiv (12*7) \pmod{31} = 22, }[/math]
[math]\displaystyle{ z_3 \equiv (16*17) \pmod{32} = 16. }[/math]

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

См. также

Литература

Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. — Сов. радио, 1968. — 439 с.
Торгашев, Валерий Антонович. Система остаточных классов и надежность ЦВМ. — М.: Сов. радио, 1973. — 118 с.
Амербаев В.М. Теоретические основы машинной арифметики. — АН КазССР, Ин-т математики и механики. Алма-Ата: Наука, 1976. — 324 с.
Шаблон:Source
Юбилейная Международная научно-техническая конференция «50 лет модулярной арифметике». — ОАО "Ангстрем", МИЭТ. — 23-25 ноября 2005 года; Москва, Зеленоград: ФИЗМАТЛИТ, 2006. — 775 с. — ISBN ISBN 5-7256-0409-8.
Amos Omondi, Benjamin Premkumar. Residue Number Systems: Theory and Implementation. — 57 Shelton Street Covent Garden London: Imperial College Press, 2007. — 296 с. — ISBN 978-1-86094-866-4.
Червяков Н. И., Евдокимов А. А., Галушкин А.И., Лавриненко И. Н. и др. Применение искусственных нейронных сетей и системы остаточных классов в криптографии. — М.: ФИЗМАТЛИТ, 2012. — 280 с. — ISBN 978-5-9221-1386-1.
Ananda Mohan, P.V. Residue Number Systems. — Cham: Springer International Publishing, 2016. — 351 с. — ISBN 978-3-319-41385-3.
Amir Sabbagh, Molahosseini, Leonel Seabra de Sousa, and Chip-Hong Chang (editors). Embedded Systems Design with Special Arithmetic and Number Systems. — Cham: Springer International Publishing, 21 March 2017. — 389 с. — ISBN 978-3-319-49742-6.

Ссылки

Статья «Модулярная арифметика» в Большой Российской Энциклопедии