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

Материал из Модулярная арифметики
(Различия между версиями)
Перейти к: навигация, поиск
Строка 2: Строка 2:
  
 
== Основные определения ==
 
== Основные определения ==
−
Системой остаточных классов называют произвольное конечное множество <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>. Тогда имеем эпиморфизм колец <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>, который индуцирует канонический изоморфизм <math>\mathbb{Z}/M\mathbb{Z}\to\prod\limits_{i=1}^{n}\mathbb{Z}/m_i\mathbb{Z}</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>. Тогда имеем эпиморфизм колец <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>, который индуцирует канонический изоморфизм <math>\mathbb{Z}/M\mathbb{Z}\cong\prod\limits_{i=1}^{n}\mathbb{Z}/m_i\mathbb{Z}</math>.
  
  
Строка 16: Строка 16:
 
=== Деление ===
 
=== Деление ===
 
Деление <math>A</math> на <math>B</math> с использованием системы остаточных классов можно выполнять не всегда. Положим, что <math>E</math>- остаток <math>AB^{-1}</math> от деления на <math>M</math>. На языке теории колец это означает, что <math>b_i,1\le i\le n</math> обратим и <math>b_i^{-1}</math>- обратный. Тогда <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>. На языке теории колец это означает, что <math>b_i,1\le i\le n</math> обратим и <math>b_i^{-1}</math>- обратный. Тогда <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>-е простое число.
 +
 +
== Литература ==
 +
# {{книга
 +
|автор        = С. Ленг
 +
|часть        =
 +
|заглавие      = Алгебра
 +
|оригинал      =
 +
|ссылка        =
 +
|издание      =
 +
|ответственный =
 +
|место        =
 +
|издательство  = [[МИР]]
 +
|год          = 1968
 +
|том          =
 +
|страницы      =
 +
|страниц      = 564
 +
|isbn          =
 +
|ref          = Ленг
 +
}}

Версия 06:41, 26 января 2013

Система остаточных классов используется для представления больших чисел N, обеспечивая таким образом более эффективные вычисления. В основе данного представления лежит изоморфизм \mathbb{Z}/m_1\cdot\ldots\cdot m_n\mathbb{Z}\cong\mathbb{Z}/m_1\times\ldots\times\mathbb{Z}/m_n , который доставляет китайская теорема об остатках.

Содержание

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

Системой остаточных классов называют произвольное конечное множество \{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. Шаблон:Книга
Источник — «http://vscripts.ru/w/index.php?title=%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D0%BE%D1%81%D1%82%D0%B0%D1%82%D0%BE%D1%87%D0%BD%D1%8B%D1%85_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%BE%D0%B2&oldid=81»
Персональные инструменты
Пространства имён

Варианты
Действия
Навигация