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

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

Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором попарно взаимно простых модулей ${\displaystyle (m_{1},\,m_{2},\,\dots ,\,m_{n})}$, то есть таких, что ${\displaystyle \gcd(m_{i},\,m_{j})=1}$ ${\displaystyle (i,\,j=0,\,1,\,\dots ,\,n;\ i\neq j)}$, называемых базисом, и произведением ${\displaystyle M=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{n},}$ так, что каждому целому числу ${\displaystyle x}$ из отрезка ${\displaystyle [0,\ M-1]}$ ставится в соответствие набор вычетов ${\displaystyle (x_{1},\,x_{2},\,\dots ,\,x_{n})}$, где

${\displaystyle x_{1}\equiv x{\pmod {m_{1}}};}$

${\displaystyle x_{2}\equiv x{\pmod {m_{2}}};}$

${\displaystyle \dots \dots \dots \dots \dots \dots \dots }$

${\displaystyle x_{n}\equiv x{\pmod {m_{n}}}.}$

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

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

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

Формула для сложения: ${\displaystyle (x_{1},x_{2},\dots ,x_{n})+(y_{1},y_{2},\dots ,y_{n})=(z_{1},z_{2},\dots ,z_{n})}$, где

${\displaystyle z_{1}\equiv (x_{1}+y_{1}){\pmod {m_{1}}};}$

${\displaystyle z_{2}\equiv (x_{2}+y_{2}){\pmod {m_{2}}};}$

${\displaystyle \dots \dots \dots \dots \dots \dots \dots \dots \dots }$

${\displaystyle z_{n}\equiv (x_{n}+y_{n}){\pmod {m_{n}}}.}$

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

${\displaystyle z_{1}\equiv (x_{1}+y_{1}){\pmod {m_{1}}}\equiv (1+0){\pmod {2}}=1;}$

${\displaystyle z_{2}\equiv (x_{2}+y_{2}){\pmod {m_{2}}}\equiv (0+2){\pmod {3}}=2;}$

${\displaystyle z_{3}\equiv (x_{3}+y_{3}){\pmod {m_{3}}}\equiv (4+4){\pmod {5}}=3;}$

${\displaystyle (z_{1},z_{2},z_{3})=(1,2,3)}$ — по таблице убеждаемся, что результат равен 23.

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

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

${\displaystyle z_{1}\equiv (x_{1}*y_{1}){\pmod {m_{1}}}\equiv (0*1){\pmod {2}}=0;}$

${\displaystyle z_{2}\equiv (x_{2}*y_{2}){\pmod {m_{2}}}\equiv (1*2){\pmod {3}}=2;}$

${\displaystyle z_{3}\equiv (x_{3}*y_{3}){\pmod {m_{3}}}\equiv (4*0){\pmod {5}}=0;}$

${\displaystyle (z_{1},z_{2},z_{3})=(0,2,0)}$ — по таблице убеждаемся, что результат равен 20.

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

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

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

Воспользуемся формулой
${\displaystyle z_{i}\equiv (x_{i}*y_{i}^{-1}){\pmod {m_{i}}}.}$

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

${\displaystyle z_{1}\equiv (16*13){\pmod {29}}=5,}$
${\displaystyle z_{2}\equiv (12*7){\pmod {31}}=22,}$
${\displaystyle z_{3}\equiv (16*17){\pmod {32}}=16.}$

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

См. также

• Сравнение по модулю
• Китайская теорема об остатках

Литература

• Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. — Сов. радио, 1968. — 439 с.
• Торгашев, Валерий Антонович. Система остаточных классов и надежность ЦВМ. — М.: Сов. радио, 1973. — 118 с.
• Амербаев В.М. Теоретические основы машинной арифметики. — АН КазССР, Ин-т математики и механики. Алма-Ата: Наука, 1976. — 324 с.
• Финько О. А. Модулярная арифметика параллельных логических вычислений: Монография — М.: ИПУ РАН, 2003. — 214 с.
• Юбилейная Международная научно-техническая конференция «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.

Ссылки

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

Эта страница в последний раз была отредактирована 20 декабря 2022 в 17:56.