Система остаточных классов — различия между версиями
Bundin (обсуждение | вклад) (→Деление) |
Bundin (обсуждение | вклад) (→Деление) |
||
| Строка 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> обратим и <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>. На языке [http://ru.wikipedia.org/wiki/Кольцо_(математика) теории колец] это означает, что <math>b_i,1\le i\le n</math> обратим и <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:05, 28 января 2013
Система остаточных классов используется для представления больших чисел 
, обеспечивая таким образом более эффективные вычисления. В основе данного представления лежит изоморфизм 
, который доставляет китайская теорема об остатках.
Содержание
Основные определения
Системой остаточных классов называют произвольное конечное множество 
, такое что 
, где 
. Пусть задана произвольная система остаточных классов 
и положим, что 
. Тогда в силу китайской теоремы об остатках имеем эпиморфизм колец 
, т.ч. 
, который индуцирует канонический изоморфизм 
.
Выполнение арифметических операций
С использованием системы остаточных классов можно выполнять основные арифметические операции.
Сложение и вычитание
Пусть 
- произвольные натуральные числа. Положим, что представляются в виде системы остаточных классов как 
и 
соответственно. Формально, 
. В силу того, что 
- изоморфизм будем иметь 
. Обозначим через 
остаток 
от деления на 
. Тогда представляется в виде системы остаточных классов как 
.
Умножение
- остаток от деления 
на . Тогда представляется в виде системы остаточных классов как 
.
Деление
Деление 
на 
с использованием системы остаточных классов можно выполнять не всегда. Положим, что 
- остаток 
от деления на . На языке теории колец это означает, что 
обратим и 
- обратный. Тогда представляется в виде 
.
Факторизация полупростых чисел
Пусть 
- полупростое число. Рассмотрим систему остаточных классов 
, где 
— 
-е простое число.
