Версия 17:00, 4 сентября 2014

Содержание

1 Теоретико-числовая база построения системы остаточных классов
2 Математические модели модулярного представления и параллельной обработки информации
3 Литература

Теоретико-числовая база построения системы остаточных классов

Напомним определение деления с остатком.

Определение

Говорят, что целое число $n$ делится на натуральное число $m$ с остатком, если имеется пара целых чисел $q$ и $r$ , таких, что $n = m \cdot q+r$ и $0\le r<m$ . $n$ называется делимым, $m$ - делителем, $q$ - неполным частным, $r$ - остатком.

Для целых чисел:

Определение

Говорят, что целое число $n \in Z$ делится на натуральное число $m \in Z$ с остатком, если имеется пара целых чисел $q$ и $r$ , таких, что $n = m \cdot q+r$ и $0\le r<|m|$ .

Пример:

48 при делении на 5 даёт остаток 3, т.к. $48=5\cdot 9+3$ , $0\le 3<5$ , -48 при делении на 5 даёт остаток 2, т.к. $-48=5\cdot (-10)+2$ , $0\le 2<5$ .

Сравнения и их основные свойства

Возьмём произвольное фиксированное натуральное число $m$ и будем рассматривать остатки при делении на $m$ различных целых чисел.

При рассмотрении свойств этих остатков и проведении операций над ними удобно ввести понятие сравнения по модулю.

Определение

Два целых числа $a$ и $b$ называются сравнимыми по модулю $m$ , если их разность $a-b$ делится без остатка на $m$ .

Символически сравнимость записывается в виде формулы (сравнения):

$a \equiv b \pmod{m}$

Число $m$ называется модулем сравнения.

Эквивалентная формулировка:

Определение

Целые числа $a$ и $b$ называются сравнимыми по модулю $m$ , если остатки от деления этих чисел на $m$ равны.

Отношение сравнимости по модулю $m$ обладает свойствами рефлексивности, симметричности и транзитивности, т.е. является отношением эквивалентности.

Отнесём все целые числа, дающие при делении на $m$ один и тот же остаток в один класс, поэтому получится $m$ различных классов по модулю $m$ . Множество всех чисел сравнимых с $a$ по модулю $m$ называется классом вычетов $a$ по модулю $m$ .

Подробнее о свойствах сравнений и классах вычетов смотри Сравнения и их основные свойства

Теорема о делении с остатком. Алгоритм Евклида

Теорема о делении с остатком

Для любых целых a и b, $b \not= 0$ , существует единственный набор целых чисел q и r, что a = bq + r и $0 \le r < |b|$ , где |b| — модуль числа b.

На этой операции основан алгоритм Евклида нахождения наибольшего общего делителя двух целых чисел.

Алгоритм Евклида для целых чисел

Пусть $a$ и $b$ — целые числа, не равные одновременно нулю, и последовательность чисел

$a > b > r_1 > r_2 > r_3 > r_4 > \cdots >r_n$

определена тем, что каждое $r_k$ — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть

$a = bq_0 + r_1$

$b = r_1q_1 + r_2$

$r_1 = r_2q_2 + r_3$

$\cdots$

$r_{k-2} = r_{k-1} q_{k-1} + r_k$

$\cdots$

$r_{n-2} = r_{n-1}q_{n-1}+ r_n$

$r_{n-1} = r_n q_n$

Тогда НОД(a,b), наибольший общий делитель $a$ и $b$ , равен $r_n$ , последнему ненулевому члену этой последовательности.

Существование таких $r_1, r_2, ...$ , то есть возможность деления с остатком $a$ на $b$ для любого целого $a$ и целого $b\ne 0$ , доказывается индукцией.

Корректность этого алгоритма вытекает из следующих двух утверждений:

Пусть $a = bq + r$ , тогда НОД ( $a$ , $b$ ) = НОД ( $b$ , $r$ ).
НОД(0, $r$ ) = $r$ для любого ненулевого $r$ (так как 0 делится на любое целое число, кроме нуля).

Китайская теорема об остатках

Фундаментальным положением, лежащим в основе модулярного представления чисел, является китайская теорема об остатках (Chinese Remainder Theorem - CRT). Например, эта теорема гарантирует, что при правильном выборе модулей СОК каждое число из динамического диапазона имеет в СОК единственное представление, и по этому представлению можно определить представленное число. В своей первоначальной формулировке эта теорема была доказана китайским математиком Сунь-Цзы приблизительно в 100 г. н.э. В современной формулировке теорема звучит так:

Теорема

Пусть $p_1, p_2, \ldots, p_k$ - попарно взаимно простые числа, большие 1, и пусть $p = p_1 \cdot p_2 \cdot \ldots \cdot p_k$ . Тогда существует единственное неотрицательное решение по модулю $p$ следующей системы сравнений:

$x \equiv a_1 \pmod{p_1}$ ,

$x \equiv a_2 \pmod{p_2}$ ,

$\ldots$ ,

$x \equiv a_k \pmod{p_k}$ .

Другими словами, отображение, которое каждому целому числу $x$ , $0\le x <p$ , ставит в соответствие кортеж $a_1, a_2,\ldots, a_k$ , где $x \equiv a_i \pmod{p_i}, i = 1, \ldots k$ является биекцией кольца $Z_P$ на декартово произведение $Z_{p_1} \times Z_{p_2} \times \ldots \times Z_{p_k}$ колец $Z_{p_1}, Z_{p_2}, \ldots, Z_{p_k}$ .

Подробности и доказательство теоремы смотри Китайская теорема об остатках.

Смотри также Китайская теорема об остатках(КТО II), Китайская теорема об остатках (КТО III).

Теоремы Эйлера и Ферма, их роль в вычислении мультипликативных обратных элементов по заданному модулю

Определение

Функция Эйлера $phi (n)$ — это количество чисел от $1$ до $n$ , взаимно простых с $n$ .

Т.е. это количество таких натуральных чисел из отрезка [1; n], наибольший общий делитель (НОД) которых с $n$ равен единице.

Tеоремa Эйлера

Если $a$ и $p$ взаимно просты, то $a^{phi(p)} \equiv 1 \pmod p$ , где $phi (n)$ - функция Эйлера.

В частном случае, когда $m$ простое, теорема Эйлера превращается в так называемую малую теорему Ферма: Частным случаем теоремы Эйлера является малая теорема Ферма.

Малая теорема Ферма

Если $p$ - простое число и $a$ - произвольное целое число, не делящееся на $p$ , то $a^{p-1} \equiv 1 \pmod p$ .

Смотри Функция Эйлера, Вычисление мультипликативных обратных элементов по заданному модулю.

Числа Мерсенна, Ферма и операции над ними

Математические модели модулярного представления и параллельной обработки информации

Версия 16:54, 4 сентября 2014 (просмотреть исходный код) Isaeva (обсуждение \| вклад) ← Предыдущая правка		Версия 17:00, 4 сентября 2014 (просмотреть исходный код) Isaeva (обсуждение \| вклад) Следующая правка →
Строка 139:		Строка 139:


−	Смотри [[Функция Эйлера\|Функция Эйлера]], [[Вычисление мультипликативных обратных элементов по заданному модулю][Вычисление мультипликативных обратных элементов по заданному модулю]].	+	Смотри [[Функция Эйлера\|Функция Эйлера]], [[Вычисление мультипликативных обратных элементов по заданному модулю\|Вычисление мультипликативных обратных элементов по заданному модулю]].

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

Версия 17:00, 4 сентября 2014

Содержание

Теоретико-числовая база построения системы остаточных классов

Сравнения и их основные свойства

Теорема о делении с остатком. Алгоритм Евклида

Китайская теорема об остатках

Теоремы Эйлера и Ферма, их роль в вычислении мультипликативных обратных элементов по заданному модулю

Числа Мерсенна, Ферма и операции над ними

Математические модели модулярного представления и параллельной обработки информации

Представление числа в системе остаточных классов. Модульные операции

Основные методы и алгоритмы перехода от позиционного представления к остаткам

Восстановление позиционного представления числа по его остаткам

Расширение диапазона представления чисел

Литература

Навигация

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

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

Варианты

Просмотры

Действия

Поиск

Навигация

Инструменты