Система остаточных классов (Vnvmybg kvmgmkcud] tlgvvkf)

Система остаточных классов (СОК) (англ. 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 \ldots \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}}};

\dots \dots \dots \dots \dots \dots \dots

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}}};

\dots \dots \dots \dots \dots \dots \dots \dots \dots

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;$