Русская Википедия:Система остаточных классов

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором попарно взаимно простых модулей <math>(m_1,\, m_2,\, \dots,\, m_n)</math>, то есть таких, что <math>\gcd(m_i,\, m_j)=1</math> <math>(i,\, j=0,\, 1,\, \dots,\, n;\ i\neq j)</math>, называемых базисом, и произведением <math>M=m_1\cdot m_2\cdot \ldots \cdot m_n,</math> так, что каждому целому числу <math>x</math> из отрезка <math>[0,\ M-1]</math> ставится в соответствие набор вычетов <math>(x_1,\, x_2,\, \dots,\, x_n)</math>, где

<math>x_1 \equiv x \pmod{m_1};</math>
<math>x_2 \equiv x \pmod{m_2};</math>
<math>\dots\dots\dots\dots\dots\dots\dots</math>
<math>x_n \equiv x \pmod{m_n}.</math>

При этом китайская теорема об остатках гарантирует однозначность (единственность) представления целых неотрицательных чисел из отрезка <math>[0,\ M-1]</math>.

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

В СОК арифметические операции (сложение, вычитание, умножение, деление) выполняются покомпонентно, если про результат известно, что он является целочисленным и также лежит в <math>[0,M-1]</math>.

Формула для сложения: <math>(x_1, x_2, \dots, x_n) + (y_1, y_2, \dots, y_n) = (z_1, z_2, \dots, z_n)</math>, где

<math>z_1 \equiv (x_1 + y_1) \pmod{m_1};</math>
<math>z_2 \equiv (x_2 + y_2) \pmod{m_2};</math>
<math>\dots\dots\dots\dots\dots\dots\dots\dots\dots</math>
<math>z_n \equiv (x_n + y_n) \pmod{m_n}.</math>

Аналогично выполняются вычитание, умножение и деление. Замечание: на деление накладываются дополнительные ограничения. Деление должно быть целочисленным, то есть делитель должен нацело делить делимое. Делитель должен быть взаимно простым со всеми модулями базиса.

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

  • отсутствие эффективных алгоритмов для сравнения чисел; обычно, сравнение осуществляется через перевод аргументов из СОК в систему счисления (полиадическую) со смешанными основаниями: <math>m_1, m_1 m_2, \dots, m_1 m_2\dots m_{n-1}</math>;
  • медленные алгоритмы взаимного преобразования представления чисел из позиционной системы счисления в СОК и обратно;
  • сложные алгоритмы деления (когда результат не является целым);
  • трудность в обнаружении переполнения.

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

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

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

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

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

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

Пример

Рассмотрим СОК с базисом <math>(2;3;5)</math>. В этом базисе можно взаимооднозначно представить числа из промежутка от <math>0</math> до <math>29</math>, так как <math>M = 2\times 3\times 5 = 30</math>. Таблица соответствия чисел из позиционной системы счисления и системы остаточных классов:

<math>0=(0;0;0)</math> <math>1=(1;1;1)</math> <math>2=(0;2;2)</math> <math>3=(1;0;3)</math> <math>4=(0;1;4)</math>
<math>5=(1;2;0)</math> <math>6=(0;0;1)</math> <math>7=(1;1;2)</math> <math>8=(0;2;3)</math> <math>9=(1;0;4)</math>
<math>10=(0;1;0)</math> <math>11=(1;2;1)</math> <math>12=(0;0;2)</math> <math>13=(1;1;3)</math> <math>14=(0;2;4)</math>
<math>15=(1;0;0)</math> <math>16=(0;1;1)</math> <math>17=(1;2;2)</math> <math>18=(0;0;3)</math> <math>19=(1;1;4)</math>
<math>20=(0;2;0)</math> <math>21=(1;0;1)</math> <math>22=(0;1;2)</math> <math>23=(1;2;3)</math> <math>24=(0;0;4)</math>
<math>25=(1;1;0)</math> <math>26=(0;2;1)</math> <math>27=(1;0;2)</math> <math>28=(0;1;3)</math> <math>29=(1;2;4)</math>

Пример сложения

Сложим два числа 9 и 14 в базисе <math>(2;3;5)</math>. Их представление в заданном базисе <math>9=(1;0;4)</math> и <math>14=(0;2;4)</math> (см. таблицу выше). Воспользуемся формулой для сложения: <math>(z_1, z_2, z_3) = (1, 0, 4) + (0, 2, 4)</math>

<math>z_1 \equiv (x_1 + y_1) \pmod{m_1} \equiv (1 + 0) \pmod{2} = 1;</math>
<math>z_2 \equiv (x_2 + y_2) \pmod{m_2} \equiv (0 + 2) \pmod{3} = 2;</math>
<math>z_3 \equiv (x_3 + y_3) \pmod{m_3} \equiv (4 + 4) \pmod{5} = 3;</math>

<math>(z_1, z_2, z_3) = (1, 2, 3)</math> — по таблице убеждаемся, что результат равен 23.

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

Умножим два числа 4 и 5 в базисе <math>(2;3;5)</math>. Их представление в заданном базисе <math>4=(0;1;4)</math> и <math>5=(1;2;0)</math> (см. табличку выше). Воспользуемся формулой для умножения: <math>(z_1, z_2, z_3) = (0, 1, 4) * (1, 2, 0)</math>

<math>z_1 \equiv (x_1 * y_1) \pmod{m_1} \equiv (0 * 1) \pmod{2} = 0;</math>
<math>z_2 \equiv (x_2 * y_2) \pmod{m_2} \equiv (1 * 2) \pmod{3} = 2;</math>
<math>z_3 \equiv (x_3 * y_3) \pmod{m_3} \equiv (4 * 0) \pmod{5} = 0;</math>

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

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

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

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

Воспользуемся формулой
<math>z_i \equiv (x_i * y_i^{-1}) \pmod{m_i}.</math>

Здесь надо сказать, что <math>y_i^{-1}*y_i=1 \pmod{m_i}</math>, что не то же самое, что просто разделить <math>x</math> на <math>y</math>.
По формуле <math>y_i^{m_i-1}=1 \pmod{m_i}</math> получаем:
<math>9^{29-2} \pmod{29} = 13,</math>
<math>9^{31-2} \pmod{31} = 7.</math>
<math>9^{32-2} \pmod{32} = 17;</math>

<math>z_1 \equiv (16*13) \pmod{29} = 5,</math>
<math>z_2 \equiv (12*7) \pmod{31} = 22,</math>
<math>z_3 \equiv (16*17) \pmod{32} = 16.</math>

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

См. также

Литература

Ссылки

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Система_остаточных_классов&oldid=10802613