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

Материал из Модулярная арифметики
Перейти к: навигация, поиск
(→‎Деление)
 
(не показано 13 промежуточных версии 2 участников)
Строка 1: Строка 1:
−
Система остаточных классов используется для представления больших чисел <math>N</math>, обеспечивая таким образом более эффективные вычисления. В основе данного представления лежит [http://ru.wikipedia.org/wiki/Изоморфизм изоморфизм] <math>\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}</math> , который доставляет [http://ru.wikipedia.org/wiki/Китайская_теорема_об_остатках китайская теорема об остатках].
+
'''Система остаточных классов (СОК)''' (от англ. [http://en.wikipedia.org/wiki/Residue_number_system Residue number system], другое название '''Модулярная арифметика''') - [http://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F#.D0.9D.D0.B5.D0.BF.D0.BE.D0.B7.D0.B8.D1.86.D0.B8.D0.BE.D0.BD.D0.BD.D1.8B.D0.B5_.D1.81.D0.B8.D1.81.D1.82.D0.B5.D0.BC.D1.8B_.D1.81.D1.87.D0.B8.D1.81.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F непозиционная система счисления]. Представление числа в системе остаточных классов основано на понятии [http://ru.wikipedia.org/wiki/%D0%A1%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE_%D0%BC%D0%BE%D0%B4%D1%83%D0%BB%D1%8E вычета] и [http://ru.wikipedia.org/wiki/%D0%9A%D0%B8%D1%82%D0%B0%D0%B9%D1%81%D0%BA%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE%D0%B1_%D0%BE%D1%81%D1%82%D0%B0%D1%82%D0%BA%D0%B0%D1%85 китайской теореме об остатках]. СОК определяется набором [http://ru.wikipedia.org/wiki/%D0%92%D0%B7%D0%B0%D0%B8%D0%BC%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%8B%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0 взаимно простых] ''модулей'' <math>(m_1, m_2, \dots, m_n)</math> с произведением <math>M=m_1\cdot m_2\cdot \dots\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>x_n \equiv x \pmod{m_n}.</math>
 +
При этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка <math>[0,M-1]</math>.
  
−
== Основные определения ==
+
== Преимущества системы остаточных классов ==
−
Системой остаточных классов называют произвольное конечное множество <math>\{m_1,\ldots ,m_n\}\subset\mathbb{N}</math>, такое что <math>\gcd\limits_{i\ne j}(m_i,m_j)=1</math>, где <math>n\in\mathbb{N}</math>. Пусть задана произвольная система остаточных классов <math>\{m_1,\ldots ,m_n\}</math> и положим, что <math>M=\prod\limits_{i=1}^{n}m_i</math>. Тогда в силу [http://ru.wikipedia.org/wiki/Китайская_теорема_об_остатках китайской теоремы об остатках] имеем [http://ru.wikipedia.org/wiki/Эпиморфизм эпиморфизм] [http://ru.wikipedia.org/wiki/Кольцо_(математика) колец] <math>\varphi: \mathbb{Z}\to\prod\limits_{i=1}^{n}\mathbb{Z}/m_i\mathbb{Z}</math>, т.ч. <math>\operatorname{Ker}\varphi=M\mathbb{Z}</math>, который индуцирует канонический [http://ru.wikipedia.org/wiki/Изоморфизм изоморфизм] <math>\mathbb{Z}/M\mathbb{Z}\cong\prod\limits_{i=1}^{n}\mathbb{Z}/m_i\mathbb{Z}</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>z_n \equiv (x_n + y_n) \pmod{m_n};</math>
 +
Аналогично выполняются вычитание, умножение и деление.
 +
'''Замечание''': на деление накладываются дополнительные ограничения: деление должно быть целочисленным, то есть делитель должен нацело делить делимое. Делитель должен быть взаимопростым со всеми модулями базиса.
  
−
== Выполнение арифметических операций ==
+
== Недостатки системы остаточных классов ==
−
С использованием системы остаточных классов можно выполнять основные арифметические операции.
+
* Возможность представления только ограниченного количества чисел.
 +
* Отсутствие эффективных алгоритмов для сравнения чисел, представленных в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям <math>(m_1, m_1\cdot m_2, \dots, m_1\cdot m_2\cdot\dots\cdot m_{n-1})</math>.
 +
* Медленные и требующие работы с большими числами реализации алгоритмов перевода из позиционной системы счисления в СОК и обратно.
 +
* Сложные алгоритмы деления (для случая, когда результат не является целым)
 +
* Трудность в обнаружении переполнения
  
−
=== Сложение и вычитание ===
+
== Применение системы остаточных классов ==
−
Пусть <math>A,B</math>- произвольные натуральные числа. Положим, что <math>A,B</math> представляются в виде системы остаточных классов как <math>(a_1,\ldots ,a_n)</math> и <math>(b_1,\ldots b_n)</math> соответственно. Формально, <math>\varphi^{-1}(a_1,\ldots ,a_n)=A, \varphi^{-1}(b_1,\ldots b_n)=B</math>. В силу того, что <math>\varphi</math>- изоморфизм будем иметь <math>\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)</math>. Обозначим через <math>C</math> остаток <math>A+B</math> от деления на <math>M</math>. Тогда <math>C</math> представляется в виде системы остаточных классов как <math>(a_1+b_1,\ldots ,a_n+b_n)</math>.
+
СОК широко используется в микроэлектронике в специализированных устройствах [ЦОС], где требуется:
 +
* контроль за ошибками, за счет введения дополнительных избыточных модулей
 +
* высокая скорость работы, которую обеспечивает параллельная реализация базовых арифметических операций
  
−
=== Умножение ===
+
== Специальные системы модулей ==
−
<math>D</math>- остаток от деления <math>A\cdot B</math> на <math>M</math>. Тогда <math>D</math> представляется в виде системы остаточных классов как <math>(a_1b_1,\ldots ,a_nb_n)</math>.
+
В модулярной арифметике существуют специальные наборы модулей, которые позволяют частично нивелировать недостатки и для которых существуют эффективные алгоритмы сравнения чисел и для прямого и обратного перевода модулярных чисел в позиционную систему счисления. Одной из самых популярных систем модулей является набор из трех взаимнопростых чисел вида '''{2<sup>n</sup>-1, 2<sup>n</sup>, 2<sup>n</sup>+1}'''
  
−
=== Деление ===
+
== Численный пример ==
−
Деление <math>A</math> на <math>B</math> с использованием системы остаточных классов можно выполнять не всегда. Положим, что <math>E</math>- остаток <math>AB^{-1}</math> от деления на <math>M</math>. На языке [http://ru.wikipedia.org/wiki/Кольцо_(математика) теории колец] это означает, что <math>b_i,1\le i\le n</math> обратим и <math>b_i^{-1}</math>- [http://ru.wikipedia.org/wiki/Обратный_элемент обратный]. Тогда <math>AB^{-1}</math> представляется в виде <math>(a_1b_1^{-1},\ldots ,a_nb_n^{-1})</math>.
+
  
−
== Факторизация полупростых чисел ==
+
== Пример ==
−
Пусть <math>X=Y\cdot Z</math>- полупростое число. Рассмотрим систему остаточных классов <math>p_i,\ldots, p_N</math>, где <math>p_i</math>— <math>i</math>-е простое число.
+
  
 +
Рассмотрим СОК с базисом <math>(2;3;5)</math>. В этом базисе можно взаимооднозначно представить числа из промежутка от <math>0</math> до <math>29</math>, так как <math>M = 2\times 3\times 5 = 30</math>. Таблица соответствия чисел из позиционной системы счисления и системы остаточных классов:
 +
{| class="wikitable"
 +
|-
 +
| <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> - результат операции в позиционной системе счисления.
−
|место        =  
+
 
−
|издательство  = [[МИР]]
+
=== Пример деления, при условии, что оно делится нацело ===
−
|год          = 1968
+
Деление может быть выполнено аналогично умножению, но только если делитель делит делимое нацело, без остатка.
−
|том          =  
+
<br />
−
|страницы      =  
+
Для модулей <math>(29;31;32)</math> разделим число 1872 на 9.<br />
−
|страниц      = 564
+
Делим <math>1872=(16;12;16)</math> на <math>9=(9;9;9)</math>.<br />
−
|isbn          =  
+
 
−
|ref          = Ленг
+
Воспользуемся формулой<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 />
 +
<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 />
 +
 
 +
 
 +
<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 - наиболее исчерпывающая информация о применении СОК с подробными примерами (на английском языке).

Текущая версия на 09:07, 21 декабря 2015

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

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

  • В СОК арифметические операции (сложение, вычитание, умножение, деление) выполняются покомпонентно, если про результат известно, что он является целочисленным и также лежит в [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}).
  • Медленные и требующие работы с большими числами реализации алгоритмов перевода из позиционной системы счисления в СОК и обратно.
  • Сложные алгоритмы деления (для случая, когда результат не является целым)
  • Трудность в обнаружении переполнения

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

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

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

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

В модулярной арифметике существуют специальные наборы модулей, которые позволяют частично нивелировать недостатки и для которых существуют эффективные алгоритмы сравнения чисел и для прямого и обратного перевода модулярных чисел в позиционную систему счисления. Одной из самых популярных систем модулей является набор из трех взаимнопростых чисел вида {2n-1, 2n, 2n+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


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 - наиболее исчерпывающая информация о применении СОК с подробными примерами (на английском языке).
Источник — «https://vscripts.ru/w/index.php?title=Система_остаточных_классов&oldid=1123»