Версия 19:54, 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$ .

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

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

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

@@ Строка 4: / Строка 4: @@
-Определение. Говорят, что целое число <math>n</math> делится на натуральное число <math>m</math> с остатком, если имеется пара целых чисел <math>q</math> и <math>r</math>, таких, что <math>n = m \cdot q+r</math> и <math>0\le r<m</math>.
+'''Определение'''
+Говорят, что целое число <math>n</math> делится на натуральное число <math>m</math> с остатком, если имеется пара целых чисел <math>q</math> и <math>r</math>, таких, что <math>n = m \cdot q+r</math> и <math>0\le r<m</math>.
 <math>n</math> называется делимым, <math>m</math> - делителем, <math>q</math> - неполным частным, <math>r</math> - остатком.
 Для целых чисел:
-Определение. Говорят, что целое число <math>n \in Z</math> делится на натуральное число <math>m \in Z</math> с остатком, если имеется пара целых чисел <math>q</math> и <math>r</math>, таких, что <math>n = m \cdot q+r</math> и <math>0\le r<|m|</math>.
+'''Определение'''
+Говорят, что целое число <math>n \in Z</math> делится на натуральное число <math>m \in Z</math> с остатком, если имеется пара целых чисел <math>q</math> и <math>r</math>, таких, что <math>n = m \cdot q+r</math> и <math>0\le r<|m|</math>.
+'''Пример''':
-Пример: '''48''' при делении на '''5''' даёт остаток '''3''', т.к. <math>48=5\cdot 9+3</math>, <math>0\le 3<5</math>, '''-48''' при делении на '''5''' даёт остаток '''2''', т.к. <math>-48=5\cdot (-10)+2</math>, <math>0\le 2<5</math>.
+'''48''' при делении на '''5''' даёт остаток '''3''', т.к. <math>48=5\cdot 9+3</math>, <math>0\le 3<5</math>, '''-48''' при делении на '''5''' даёт остаток '''2''', т.к. <math>-48=5\cdot (-10)+2</math>, <math>0\le 2<5</math>.
@@ Строка 21: / Строка 29: @@
-Определение. Два целых числа <math> a </math> и <math> b </math> называются '''сравнимыми по модулю <math> m </math>''', если их разность <math> a-b </math> делится без остатка на <math> m </math>.
+'''Определение'''
+Два целых числа <math> a </math> и <math> b </math> называются '''сравнимыми по модулю <math> m </math>''', если их разность <math> a-b </math> делится без остатка на <math> m </math>.
 Символически сравнимость записывается в виде формулы ('''сравнения'''):
 : <math>a \equiv b \pmod{m}</math>
@@ Строка 30: / Строка 42: @@
 Эквивалентная формулировка:
-Определение. Целые числа <math> a </math> и <math> b </math> называются '''сравнимыми по модулю <math> m </math>''', если остатки от деления этих чисел на <math> m </math> равны.
+'''Определение'''
+Целые числа <math> a </math> и <math> b </math> называются '''сравнимыми по модулю <math> m </math>''', если остатки от деления этих чисел на <math> m </math> равны.
 Отношение сравнимости по модулю <math> m </math> обладает свойствами рефлексивности, симметричности и транзитивности, т.е. является отношением эквивалентности.
@@ Строка 42: / Строка 57: @@
 '''Теорема о делении с остатком'''
-для любых целых ''a'' и ''b'',
-<math>b \not= 0</math>, существует единственный набор целых чисел ''q'' и ''r'', что a = bq + r и <math>0 \le r < |b|</math>, где |''b''| — модуль числа ''b''.
+Для любых целых ''a'' и ''b'', <math>b \not= 0</math>, существует единственный набор целых чисел ''q'' и ''r'', что a = bq + r и <math>0 \le r < |b|</math>, где |''b''| — модуль числа ''b''.
 На этой операции основан алгоритм Евклида нахождения наибольшего общего делителя двух целых чисел.
@@ Строка 65: / Строка 81: @@
 Тогда НОД(''a'',''b''), наибольший общий делитель <math>a</math> и <math>b</math>, равен
 <math>r_n</math>, последнему ненулевому члену этой последовательности.
 '''Существование''' таких <math>r_1, r_2, ...</math>, то есть возможность деления с остатком <math>a</math> на <math>b</math> для любого целого <math>a</math> и целого <math>b\ne 0</math>, доказывается индукцией.
 '''Корректность''' этого алгоритма вытекает из следующих двух утверждений:
 * Пусть <math>a = bq + r</math>, тогда НОД (<math>a</math>, <math>b</math>) = НОД (<math>b</math>, <math>r</math>).
 * НОД(0,<math>r</math>) = <math>r</math> для любого ненулевого <math>r</math> (так как 0 делится на любое целое число, кроме нуля).
@@ Строка 82: / Строка 100: @@
 В современной формулировке теорема звучит так:
-Теорема.
+'''Теорема'''
 Пусть <math>p_1, p_2, \ldots, p_k</math> - попарно взаимно простые числа, большие 1, и пусть <math>p = p_1 \cdot p_2 \cdot \ldots  \cdot p_k</math>. Тогда существует единственное неотрицательное решение по модулю <math>p</math> следующей системы сравнений:
@@ Строка 89: / Строка 107: @@
 : <math>\ldots</math>,
 : <math>x \equiv a_k \pmod{p_k}</math>.
 Другими словами, отображение, которое каждому целому числу <math>x</math>, <math>0\le x <p</math>, ставит в соответствие кортеж <math>a_1, a_2,\ldots, a_k</math>, где <math>x \equiv a_i \pmod{p_i}, i = 1, \ldots k</math> является биекцией кольца <math>Z_P</math> на декартово произведение <math>Z_{p_1} \times Z_{p_2} \times \ldots \times Z_{p_k}</math>  колец <math>Z_{p_1}, Z_{p_2}, \ldots, Z_{p_k}</math>.
@@ Строка 97: / Строка 116: @@
 == Теоремы Эйлера и Ферма, их роль в вычислении мультипликативных обратных элементов по заданному модулю ==
+'''Определение'''
+Функция Эйлера <math>phi (n)</math> — это количество чисел от <math>1</math> до <math>n</math>, взаимно простых с <math>n</math>.
+Т.е. это количество таких натуральных чисел из отрезка [1; n], наибольший общий делитель (НОД) которых с <math>n</math> равен единице.
+'''Tеоремa Эйлера'''
+Если <math>a</math> и <math>p</math> взаимно просты, то <math>a^{phi(p)} \equiv 1 \pmod p</math>, где <math>phi (n)</math> - функция Эйлера.
+В частном случае, когда <math>m</math> простое, теорема Эйлера превращается в так называемую малую теорему Ферма:
+Частным случаем теоремы Эйлера является малая теорема Ферма.
+'''Малая теорема Ферма'''
+Если <math>p</math> - простое число и <math>a</math> - произвольное целое число, не делящееся на <math>p</math>, то <math>a^{p-1} \equiv 1 \pmod p </math>.
+Смотри [[Функция Эйлера|Функция Эйлера]], [[Вычисление мультипликативных обратных элементов по заданному модулю][Вычисление мультипликативных обратных элементов по заданному модулю]].
 == Числа Мерсенна, Ферма и операции над ними ==

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

Версия 19:54, 4 сентября 2014

Содержание

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

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

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

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

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

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

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

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

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

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

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

Литература

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

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

Варианты

Просмотры

Действия

Поиск

Навигация