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

Версия 10:31, 28 января 2013

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

Литература

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

@@ Строка 14: / Строка 14: @@
 === Деление ===
-Деление <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> [http://ru.wikipedia.org/wiki/Обратный_элемент обратим] и <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>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> [http://ru.wikipedia.org/wiki/Обратимый_элемент обратим] и <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>.
 == Факторизация полупростых чисел ==

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

Версия 10:31, 28 января 2013

Содержание

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

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

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

Умножение

Деление

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

Литература

Навигация

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

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

Варианты

Просмотры

Действия

Поиск

Навигация

Инструменты