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

Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках . СОК определяется набором попарно взаимно простых модулей ${\displaystyle (m_{1},\,m_{2},\,\dots ,\,m_{n})}$ , то есть таких, что gcd (m i , m j) = 1 {\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 с.
• . — ОАО "Ангстрем" , МИЭТ . — 23-25 ноября 2005 года; Москва, Зеленоград: ФИЗМАТЛИТ , 2006. — 775 с. — ISBN ISBN 5-7256-0409-8 .
• Amos Omondi, Benjamin Premkumar. . — 57 Shelton Street Covent Garden London: , 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 .

Ссылки