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

'''Система остаточных классов (СОК)''' ({{lang-en|residue number system}}) — [[система счисления]], основанная на [[модулярная арифметика|модулярной арифметике]].

Представление числа в системе остаточных классов основано на понятии [[Сравнение по модулю|вычета]] и [[Китайская теорема об остатках|китайской теореме об остатках]]. СОК определяется набором попарно [[Взаимно простые числа|взаимно простых]] ''модулей'' <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 (компьютер) | чехословацкая ламповая ЭВМ «EPOS»]], советская военная многопроцессорная суперЭВМ [[5Э53]], предназначенная для решения задач [[Противоракетная оборона | противоракетной обороны]].

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

== Пример ==
Рассмотрим СОК с базисом <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> — результат операции в позиционной системе счисления.

=== Пример деления, при условии, что возможно деление нацело ===
Деление может быть выполнено аналогично умножению, но только если делитель делит делимое нацело, без остатка.
<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>

Здесь надо сказать, что <math>y_i^{-1}*y_i=1 \pmod{m_i}</math>, что не то же самое, что просто разделить <math>x</math> на <math>y</math>.<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>

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

== См. также ==
* [[Сравнение по модулю]]
* [[Китайская теорема об остатках]]

== Литература ==
* {{книга
|автор = [[Акушский, Израиль Яковлевич|Акушский И.Я.]],  [[Юдицкий, Давлет Исламович|Юдицкий Д.И.]]
|заглавие = Машинная арифметика в остаточных классах
|ссылка = https://search.rsl.ru/ru/record/01005937678
|ответственный=|издание = 
|место = 
|издательство =  [[Список издательств СССР по кодам|Сов. радио]]
|год = 1968
|страницы = 
|страниц= 439
|isbn = 
|isbn2=}}
* {{книга
|автор = Торгашев, Валерий Антонович.
|заглавие = Система остаточных классов и надежность ЦВМ
|ссылка = https://search.rsl.ru/ru/record/01008412713
|издание = 
|место = М.
|издательство = [[Список издательств СССР по кодам|Сов. радио]]
|год = 1973
|страниц = 118
|isbn = 
}}
* {{книга
|автор = [[Амербаев, Вильжан Мавлютинович|Амербаев В.М.]]
|заглавие = Теоретические основы машинной арифметики
|ссылка = http://search.rsl.ru/ru/record/01007734237
|издание = 
|место = АН КазССР, Ин-т математики и механики. Алма-Ата
|издательство =  [[Наука (издательство)|Наука]]
|год = 1976
|страниц = 324
|isbn = 
}}
* {{source|Q53341250 |ref=Финько|ref-year=2003}} <!-- Модулярная арифметика параллельных логических вычислений: монография-->
* {{книга
|автор = 
|заглавие = Юбилейная Международная научно-техническая конференция «50 лет модулярной арифметике»
|ссылка = http://www.computer-museum.ru/histussr/sokconf0.htm
|издание = [[Ангстрем (компания)|ОАО "Ангстрем"]], [[Национальный исследовательский университет «Московский институт электронной техники»|МИЭТ]]
|место = 23-25 ноября 2005 года; Москва, Зеленоград
|издательство =  [[Физматлит|ФИЗМАТЛИТ]]
|год = 2006
|страниц = 775
|isbn = ISBN 5-7256-0409-8
}}
* {{книга
|автор = Amos Omondi, Benjamin Premkumar
|заглавие = Residue Number Systems: Theory and Implementation
|ссылка = http://lib.mexmat.ru/books/132218
|издание = 
|место = 57 Shelton Street Covent Garden London
|издательство =  [https://istina.msu.ru/publishers/58820/ Imperial College Press]
|год = 2007
|страниц = 296
|isbn = 978-1-86094-866-4
}}
* {{книга
|автор = Червяков Н. И., Евдокимов А. А., [[Галушкин, Александр Иванович (учёный)|Галушкин А.И.]], Лавриненко И. Н. и др.
|заглавие = Применение искусственных нейронных сетей и системы остаточных классов в криптографии
|ссылка = http://www.rfbr.ru/rffi/ru/books/o_1782371
|издание = 
|место = М.
|издательство =  [[Физматлит|ФИЗМАТЛИТ]]
|год = 2012
|страниц = 280
|isbn = 978-5-9221-1386-1
}}
* {{книга
|автор = Ananda Mohan, P.V.
|заглавие = Residue Number Systems
|ссылка =
|издание = 
|место = Cham
|издательство = [[Springer Science+Business Media|Springer International Publishing]]
|год = 2016
|страниц = 351
|isbn = 978-3-319-41385-3
}}
* {{книга
|автор = Amir Sabbagh, Molahosseini, Leonel Seabra de Sousa, and Chip-Hong Chang (editors)
|заглавие = Embedded Systems Design with Special Arithmetic and Number Systems
|ссылка = 
|издание = 
|место = Cham
|издательство =  [[Springer Science+Business Media|Springer International Publishing]]
|год = 21 March 2017
|страниц = 389
|isbn = 978-3-319-49742-6
}}

== Ссылки ==
* [http://bigenc.ru/mathematics/text/3954960 Статья «Модулярная арифметика» в Большой Российской Энциклопедии]

[[Категория:Теория чисел]]