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

Система остаточных классов (СОК) (от англ. Residue number system, другое название Модулярная арифметика) — непозиционная система счисления. Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором попарно взаимно простых модулей $(m_{1},\,m_{2},\,\dots ,\,m_{n})$, то есть таких, что $\gcd(m_{i},\,m_{j})=1$ $(i,\,j=0,\,1,\,\dots ,\,n;\ i\neq j)$, называемых базисом, с произведением $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}m_{2},\dots ,m_{1}m_{2}\dots m_{n-1}$;
• медленные алгоритмы взаимного преобразования представления чисел из позиционной системы счисления в СОК и обратно;
• сложные алгоритмы деления (когда результат не является целым);
• трудность в обнаружении переполнения.

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

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

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

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

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

В модулярной арифметике существуют специальные наборы модулей, которые позволяют частично нивелировать недостатки и для которых существуют эффективные алгоритмы сравнения чисел и для прямого и обратного перевода модулярных чисел в позиционную систему счисления. Одной из самых популярных систем модулей является набор из трех попарно взаимно простых чисел вида {2ⁿ−1, 2ⁿ, 2ⁿ+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 — наиболее исчерпывающая информация о применении СОК с подробными примерами (на английском языке).
• Теоретические основы машинной арифметики [Текст] / В.М. Амербаев; АН КазССР, Ин-т математики и механики. - Алма-Ата : Наука, 1976. - 324 с.; 21 см.
• Червяков Н. И., Евдокимов А. А., Галушкин А.И., Лавриненко И. Н. и др. Применение искусственных нейронных сетей и системы остаточных классов в криптографии — М.: ФИЗМАТЛИТ, 2012. — 280 c. — ISBN 978-5-9221-1386-1.
• Юбилейная Международная научно-техническая конференция «50 лет модулярной арифметике»; 23-25 ноября 2005 года (МИЭТ, Москва-Зеленоград) — М.: ОАО "Ангстрем", МИЭТ, 2006, — 775 с. ISBN 5-7256-0409-8.
• Монография «Модулярная арифметика параллельных логических вычислений», Финько О.А. / Под редакцией профессора В.Д. Малюгина; М.: Институт проблем управления имени В.А. Трапезникова РАН, 2003. — 214 с.
• Embedded Systems Design with Special Arithmetic and Number Systems. — Cham: Springer International Publishing, 21 March 2017. — С. 389. — ISBN 978-3-319-49742-6.

Ссылки

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