Система остаточных классов — различия между версиями

Версия 15:48, 23 апреля 2013

Система остаточных классов (СОК) (от англ. Residue number system, другое название Модулярная арифметика) - непозиционная система счисления. Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором взаимно простых модулей $(m_1, m_2, \dots, m_n)$ с произведением $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 \pmod{m_1};$

$x_2 \equiv x \pmod{m_2};$

…

$x_n \equiv x \pmod{m_n}.$

При этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка $[0,M-1]$ .

Содержание

1 Преимущества системы остаточных классов
2 Недостатки системы остаточных классов
3 Применение системы остаточных классов
4 Специальные системы модулей
5 Основные определения
6 Выполнение арифметических операций
7 Факторизация полупростых чисел
8 Численный пример
9 Пример
10 Ссылки

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

В СОК арифметические операции (сложение, вычитание, умножение, деление) выполняются покомпонентно, если про результат известно, что он является целочисленным и также лежит в $[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};$

...

$z_n \equiv (x_n + y_n) \pmod{m_n};$

Аналогично выполняются вычитание, умножение и деление.

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

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

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

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

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

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

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

Основные определения

Система остаточных классов используется для представления больших чисел $N$ , обеспечивая таким образом более эффективные вычисления. В основе данного представления лежит изоморфизм $\mathbb{Z}/m_1\cdot\ldots\cdot m_n\mathbb{Z}\cong\mathbb{Z}/m_1\mathbb{Z}\times\ldots\times\mathbb{Z}/m_n\mathbb{Z}$ , который доставляет китайская теорема об остатках.

Системой остаточных классов называют произвольное конечное множество $\{m_1,\ldots ,m_n\}\subset\mathbb{N}$ , такое что $\gcd\limits_{i\ne j}(m_i,m_j)=1$ , где $n\in\mathbb{N}$ . Пусть задана произвольная система остаточных классов $\{m_1,\ldots ,m_n\}$ и положим, что $M=\prod\limits_{i=1}^{n}m_i$ . Тогда в силу китайской теоремы об остатках имеем эпиморфизм колец $\varphi: \mathbb{Z}\to\prod\limits_{i=1}^{n}\mathbb{Z}/m_i\mathbb{Z}$ , т.ч. $\operatorname{Ker}\varphi=M\mathbb{Z}$ , который индуцирует канонический изоморфизм $\mathbb{Z}/M\mathbb{Z}\cong\prod\limits_{i=1}^{n}\mathbb{Z}/m_i\mathbb{Z}$ .

Выполнение арифметических операций

С использованием системы остаточных классов можно выполнять основные арифметические операции.

Сложение и вычитание

Пусть $A,B$ - произвольные натуральные числа. Положим, что $A,B$ представляются в виде системы остаточных классов как $(a_1,\ldots ,a_n)$ и $(b_1,\ldots b_n)$ соответственно. Формально, $\varphi^{-1}(a_1,\ldots ,a_n)=A, \varphi^{-1}(b_1,\ldots b_n)=B$ . В силу того, что $\varphi$ - изоморфизм будем иметь $\varphi^{-1}((a_1,\ldots ,a_n)+(b_1,\ldots b_n))=\varphi^{-1}(a_1,\ldots ,a_n)+\varphi^{-1}(b_1,\ldots b_n)$ . Обозначим через $C$ остаток $A+B$ от деления на $M$ . Тогда $C$ представляется в виде системы остаточных классов как $(a_1+b_1,\ldots ,a_n+b_n)$ .

Умножение

$D$ - остаток от деления $A\cdot B$ на $M$ . Тогда $D$ представляется в виде системы остаточных классов как $(a_1b_1,\ldots ,a_nb_n)$ .

Деление

Деление $A$ на $B$ с использованием системы остаточных классов можно выполнять не всегда. Положим, что $E$ - остаток $AB^{-1}$ от деления на $M$ . На языке теории колец это означает, что $b_i,1\le i\le n$ обратим и $b_i^{-1}$ - обратный. Тогда $AB^{-1}$ представляется в виде $(a_1b_1^{-1},\ldots ,a_nb_n^{-1})$ .

Факторизация полупростых чисел

Пусть $X=Y\cdot Z$ - полупростое число. Рассмотрим систему остаточных классов $p_i,\ldots, p_N$ , где $p_i$ — $i$ -е простое число.

Численный пример

Пример

Рассмотрим СОК с базисом $(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$

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

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

Ссылки

Книга "Residue Number Systems: Theory and Implementation", Amos Omondi, Benjamin Premkumar - наиболее исчерпывающая информация о применении СОК с подробными примерами (на английском языке).

@@ Строка 19: / Строка 19: @@
 * Возможность представления только ограниченного количества чисел.
 * Отсутствие эффективных алгоритмов для сравнения чисел, представленных в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям <math>(m_1, m_1\cdot m_2, \dots, m_1\cdot m_2\cdot\dots\cdot m_{n-1})</math>.
-* Сложные реализации алгоритмов перевода из позиционной системы счисления в СОК и обратно.
+* Медленные и требующие работы с большими числами реализации алгоритмов перевода из позиционной системы счисления в СОК и обратно.
+* Сложные алгоритмы деления (для случая, когда результат не является целым)
+* Трудность в обнаружении переполнения
 == Применение системы остаточных классов ==
@@ Строка 25: / Строка 27: @@
 * контроль за ошибками, за счет введения дополнительных избыточных модулей
 * высокая скорость работы, которую обеспечивает параллельная реализация базовых арифметических операций
+== Специальные системы модулей ==
+В модулярной арифметике существуют специальные наборы модулей, которые позволяют частично нивелировать недостатки и для которых существуют эффективные алгоритмы сравнения чисел и для прямого и обратного перевода модулярных чисел в позиционную систему счисления. Одной из самых популярных систем модулей является набор из трех взаимнопростых чисел вида '''{2<sup>n</sup>-1, 2<sup>n</sup>, 2<sup>n</sup>+1}'''
 == Основные определения ==
@@ Строка 84: / Строка 89: @@
 Замечание: если бы мы умножали или складывали числа, которые дали в результате умножения число больше или равное <math>M = 30</math>, то полученный результат <math>RES \equiv REAL \pmod{M}</math>, где <math>REAL</math> - результат операции в позиционной системе счисления.
-== Литература ==
+=== Пример деления, при условии, что оно делится нацело ===
-# {{книга
+Деление может быть выполнено аналогично умножению, но только если делитель делит делимое нацело, без остатка.
- |автор         = С. Ленг
+<br />
- |часть         =
+Для модулей <math>(29;31;32)</math> разделим число 1872 на 9.<br />
- |заглавие      = Алгебра
+Делим <math>1872=(16;12;16)</math> на <math>9=(9;9;9)</math>.<br />
- |оригинал      =
- |ссылка        =
+Воспользуемся формулой<br />
- |издание       =
+<math>z_i \equiv (x_i * y_i^{-1}) \pmod{m_i};</math>
- |ответственный =
+<br /><br />
- |место         =
+Здесь надо сказать, что <math>y_i^{-1}*y_i=1 \pmod{m_i}</math>, что не то же самое, что просто разделить x на y.<br />
- |издательство  = [[МИР]]
+По формуле <math>y_i^{m_i-1}=1 \pmod{m_i}</math> получаем<br />
- |год           = 1968
+<math>9^{29-2} \pmod{29} = 13</math><br />
- |том           =
+<math>9^{31-2} \pmod{31} = 7</math><br />
- |страницы      =
+<math>9^{32-2} \pmod{32} = 17</math><br />
- |страниц       = 564
- |isbn          =
- |ref           = Ленг
+<math>z_1 \equiv (16*13) \pmod{29} = 5</math><br />
-}}
+<math>z_2 \equiv (12*7) \pmod{31} = 22</math><br />
+<math>z_3 \equiv (16*17) \pmod{32} = 16</math><br />
+<br />
+Это и есть правильный результат - число 208. Однако такой результат можно получить только если известно, что деление производится без остатка.
+== Ссылки ==
+* Книга "Residue Number Systems: Theory and Implementation", Amos Omondi, Benjamin Premkumar - наиболее исчерпывающая информация о применении СОК с подробными примерами (на английском языке).