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

Система остаточных классов (СОК) (Шаблон:Lang-en) — система счисления, основанная на модулярной арифметике.

Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором попарно взаимно простых модулей $(m_1,m_2,\dots ,m_n)$, то есть таких, что $\gcd (m_i,m_j)=1$ $(i,j=0,1,\dots ,n;i\ne 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(\mathrm{mod}{m}_1);$

$x_2\equiv x(\mathrm{mod}{m}_2);$

$\dots \dots \dots \dots \dots \dots \dots$

$x_n\equiv x(\mathrm{mod}{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)(\mathrm{mod}{m}_1);$

$z_2\equiv (x_2+y_2)(\mathrm{mod}{m}_2);$

$\dots \dots \dots \dots \dots \dots \dots \dots \dots$

$z_n\equiv (x_n+y_n)(\mathrm{mod}{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)(\mathrm{mod}{m}_1)\equiv (1+0)(\mathrm{mod}2)=1;$

$z_2\equiv (x_2+y_2)(\mathrm{mod}{m}_2)\equiv (0+2)(\mathrm{mod}3)=2;$

$z_3\equiv (x_3+y_3)(\mathrm{mod}{m}_3)\equiv (4+4)(\mathrm{mod}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)(\mathrm{mod}{m}_1)\equiv (0*1)(\mathrm{mod}2)=0;$

$z_2\equiv (x_2*y_2)(\mathrm{mod}{m}_2)\equiv (1*2)(\mathrm{mod}3)=2;$

$z_3\equiv (x_3*y_3)(\mathrm{mod}{m}_3)\equiv (4*0)(\mathrm{mod}5)=0;$

$(z_1,z_2,z_3)=(0,2,0)$ — по таблице убеждаемся, что результат равен 20.

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

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

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

Воспользуемся формулой
$z_i\equiv (x_i*y_i^{-1})(\mathrm{mod}{m}_i).$

Здесь надо сказать, что $y_i^{-1}*y_i=1(\mathrm{mod}{m}_i)$, что не то же самое, что просто разделить $x$ на $y$.
По формуле $y_i^{m_i-1}=1(\mathrm{mod}{m}_i)$ получаем:
$9^{29-2}(\mathrm{mod}29)=13,$
$9^{31-2}(\mathrm{mod}31)=7.$
$9^{32-2}(\mathrm{mod}32)=17;$

$z_1\equiv (16*13)(\mathrm{mod}29)=5,$
$z_2\equiv (12*7)(\mathrm{mod}31)=22,$
$z_3\equiv (16*17)(\mathrm{mod}32)=16.$

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Source
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга

Ссылки

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