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

Материал из Модулярная арифметики
Перейти к: навигация, поиск
Строка 8: Строка 8:
 
== Преимущества системы остаточных классов ==
 
== Преимущества системы остаточных классов ==
 
* В СОК арифметические операции (сложение, вычитание, умножение, деление) выполняются покомпонентно, если про результат известно, что он является целочисленным и также лежит в <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>z_n \equiv (x_n + y_n) \pmod{m_n};</math>
 +
Аналогично выполняются вычитание, умножение и деление.
  
 
== Недостатки системы остаточных классов ==
 
== Недостатки системы остаточных классов ==
Строка 40: Строка 47:
  
 
== Численный пример ==
 
== Численный пример ==
 +
 +
== Пример ==
  
 
Рассмотрим СОК с базисом <math>(2;3;5)</math>. В этом базисе можно взаимооднозначно представить числа из промежутка от <math>0</math> до <math>29</math>, так как <math>M = 2\times 3\times 5 = 30</math>. Таблица соответствия чисел из позиционной системы счисления и системы остаточных классов:
 
Рассмотрим СОК с базисом <math>(2;3;5)</math>. В этом базисе можно взаимооднозначно представить числа из промежутка от <math>0</math> до <math>29</math>, так как <math>M = 2\times 3\times 5 = 30</math>. Таблица соответствия чисел из позиционной системы счисления и системы остаточных классов:
Строка 58: Строка 67:
  
 
=== Пример сложения ===
 
=== Пример сложения ===
 +
Сложим два числа 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> - результат операции в позиционной системе счисления.
  
 
== Литература ==
 
== Литература ==

Версия 06:43, 11 февраля 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].

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

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

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

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

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

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

Система остаточных классов используется для представления больших чисел 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 - результат операции в позиционной системе счисления.

Литература

  1. Шаблон:Книга
Источник — «https://vscripts.ru/w/index.php?title=Система_остаточных_классов&oldid=117»