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

Система остаточных классов (СОК) (от , другое названиеМодулярная арифметика) — непозиционная система счисления.Представление числа в системе остаточных классов основано на понятиивычета и китайской теореме об остатках. СОК определяется набором попарновзаимно простых модулей (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. Однако такой результатможно получить, только если известно, что деление производится безостатка.