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

Система остаточных классов (СОК) (от , другое название Модулярная арифметика) — непозиционная система счисления. Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором попарно взаимно простых модулей (m1,m2,,mn), то есть таких, что gcd(mi,mj)=1 (i,j=0,1,,n; ij), называемых базисом, с произведением M=m1m2mn, так, что каждому целому числу x из отрезка [0, M1] ставится в соответствие набор вычетов (x1,x2,,xn), где

x1x(modm1);
x2x(modm2);
 \ldots
xnx(modmn).
  При этом китайская теорема об остатках гарантирует однозначность (единственность) представления целых неотрицательных чисел из отрезка [0, M1].

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



  • В СОК арифметические операции (сложение, вычитание, умножение, деление) выполняются покомпонентно, если про результат известно, что он является целочисленным и также лежит в [0,M1].

 Формула для сложения: (x1,x2,,xn)+(y1,y2,,yn)=(z1,z2,,zn), где

z1(x1+y1)(modm1);
z2(x2+y2)(modm2);
 \ldots
zn(xn+yn)(modmn);
  Аналогично выполняются вычитание, умножение и деление. Замечание: на деление накладываются дополнительные ограничения. Деление должно быть целочисленным, то есть делитель должен нацело делить делимое. Делитель должен быть взаимопростым со всеми модулями базиса.

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



  • Возможность представления только ограниченного количества чисел.
  • Отсутствие эффективных алгоритмов для сравнения чисел, представленных в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям (m1,m1m2,,m1m2mn1).
  • Медленные и требующие работы с большими числами реализации алгоритмов перевода из позиционной системы счисления в СОК и обратно.
  • Сложные алгоритмы деления (для случая, когда результат не является целым)
  • Трудность в обнаружении переполнения

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


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

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

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

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


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

Пример


 Рассмотрим СОК с базисом (2;3;5). В этом базисе можно взаимооднозначно представить числа из промежутка от 0 до 29, так как M=2×3×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) (см. табличку выше). Воспользуемся формулой для сложения: (z1,z2,z3)=(1,0,4)+(0,2,4)

z1(x1+y1)(modm1)(1+0)(mod2)=1;
z2(x2+y2)(modm2)(0+2)(mod3)=2;
z3(x3+y3)(modm3)(4+4)(mod5)=3;
(z1,z2,z3)=(1,2,3) — по таблице убеждаемся, что результат равен 23.

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


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

z1(x1y1)(modm1)(01)(mod2)=0;
z2(x2y2)(modm2)(12)(mod3)=2;
z3(x3y3)(modm3)(40)(mod5)=0;
(z1,z2,z3)=(0,2,0) — по таблице убеждаемся, что результат равен 20.
 Замечание: если бы мы умножали или складывали числа, которые дали в результате умножения число больше или равное M=30, то полученный результат RESREAL(modM), где REAL — результат операции в позиционной системе счисления.

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


 Деление может быть выполнено аналогично умножению, но только если делитель делит делимое нацело, без остатка.\\Для модулей (29;31;32) разделим число 1872 на 9.\\Делим 1872=(16;12;16) на 9=(9;9;9).\\ Воспользуемся формулой\\zi(xiyi1)(modmi);\\\\Здесь надо сказать, что yi1yi=1(modmi), что не то же самое, что просто разделить x на y.\\По формуле yimi1=1(modmi) получаем\\9292(mod29)=13\\9312(mod31)=7\\9322(mod32)=17\\
z1(1613)(mod29)=5\\z2(127)(mod31)=22\\z3(1617)(mod32)=16\\ Это и есть правильный результат — число 208. Однако такой результат можно получить, только если известно, что деление производится без остатка.