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

Версия 10:29, 4 февраля 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 Литература

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

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

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

Возможность представления только ограниченного количества чисел.
Отсутствие эффективных алгоритмов для сравнения чисел, представленных в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям $(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$ -е простое число.

Литература

Шаблон:Книга

@@ Строка 1: / Строка 1: @@
 '''Система остаточных классов (СОК)''' (от англ. [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 \equiv x_1 \pmod{m_1};</math>
+: <math>x_1 \equiv x \pmod{m_1};</math>
-: <math>x \equiv x_2 \pmod{m_2};</math>
+: <math>x_2 \equiv x \pmod{m_2};</math>
 : …
-: <math>x \equiv x_n \pmod{m_n}.</math>
+: <math>x_n \equiv x \pmod{m_n}.</math>
 При этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка <math>[0,M-1]</math>.

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

Версия 10:29, 4 февраля 2013

Содержание

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

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

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

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

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

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

Умножение

Деление

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

Литература

Персональные инструменты

Пространства имён

Варианты

Просмотры

Действия

Поиск

Навигация