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

Материал из Модулярная арифметики
(Различия между версиями)
Перейти к: навигация, поиск
Строка 165: Строка 165:
 
При <math>n = 0, 1, 2, 3, 4</math> числа Ферма простые: <math>3, 5, 17, 257, 65537</math>. Известно, что для <math>5\le n \le 32</math> числа <math>F_n</math> являются составными. На 2014 г. не найдено ни одного простого числа такого вида для <math>n>4</math>.
 
При <math>n = 0, 1, 2, 3, 4</math> числа Ферма простые: <math>3, 5, 17, 257, 65537</math>. Известно, что для <math>5\le n \le 32</math> числа <math>F_n</math> являются составными. На 2014 г. не найдено ни одного простого числа такого вида для <math>n>4</math>.
  
Все числа Мерсенна и Ферма – взаимно простые.
 
  
 
+
Все числа Мерсенна и Ферма – взаимно простые. Кроме того, для модулей СОК вида <math>M_n = 2^n - 1</math>, <math>M_n = 2^n + 1</math> легко реализуется преобразование и арифметические операции. Поэтому эффективно выбирать модули СОК в виде чисел Мерсенна и Ферма.  
Для модулей СОК вида <math>M_n = 2^n - 1</math>, <math>M_n = 2^n + 1</math> легко реализуется преобразование и арифметические операции. Поэтому эффективно выбирать модули СОК в виде чисел Мерсенна и Ферма.  
+
  
 
Смотри [[Числа Мерсенна и Ферма|Числа Мерсенна и Ферма]].
 
Смотри [[Числа Мерсенна и Ферма|Числа Мерсенна и Ферма]].

Версия 16:41, 10 сентября 2014

Содержание

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

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


Определение

Говорят, что целое число 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 .


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


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

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

Определение

Числа Мерсенна — числа вида M_n = 2^n - 1, где n — натуральное число. Названы в честь французского математика Марена Мерсенна.

Иногда числами Мерсенна называют только числа M_n с нечетными или простыми индексами n.

Множества простых чисел в этих последовательностях совпадают, а потому понятие простого числа Мерсенна не зависит от того, как именно определяются числа Мерсенна.

При простых значениях n = p число может оказаться простым, но может быть составным. Например, при p = 2, 3, 5, 7, 13, 17, 19 мы получаем простые числа Мерсенна: 3, 7, 31, 127, 8191, 131071, а при p = 11, 23, 29 числа 2^p - 1 - составные.


Определение

Числа Ферма — числа вида F_n=2^{2^n}+1, где n — неотрицательное целое число.

При n = 0, 1, 2, 3, 4 числа Ферма простые: 3, 5, 17, 257, 65537. Известно, что для 5\le n \le 32 числа F_n являются составными. На 2014 г. не найдено ни одного простого числа такого вида для n>4.


Все числа Мерсенна и Ферма – взаимно простые. Кроме того, для модулей СОК вида M_n = 2^n - 1, M_n = 2^n + 1 легко реализуется преобразование и арифметические операции. Поэтому эффективно выбирать модули СОК в виде чисел Мерсенна и Ферма.

Смотри Числа Мерсенна и Ферма.

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

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

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

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

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

Литература


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

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