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

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

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

Определение

Говорят, что целое число $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$ легко реализуется преобразование и арифметические операции. Поэтому эффективно выбирать модули СОК в виде чисел Мерсенна и Ферма.

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

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

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

Система остаточных классов обладает одной особенностью, которую можно отнести к недостаткам этой системы: нельзя визуально определить величину числа, представленного в СОК, а следовательно затруднительно и выполнение таких операций, как сравнение чисел, определение знака числа. Один из путей решения этой проблемы состоит в преобразовании чисел из СОК в позиционную систему счисления. Оценим существующие способы перевода, как традиционные: метод ортогональных базисов; перевод числа в обобщенную позиционную систему (ОПС), так и недавно появившиеся интервальные методы перевода.

Метод ортогональных базисов

Метод восстановления числа по его остаткам был найден еще в Китае две тысячи лет назад. Основой этого метода является теорема, названная Китайской теоремой об остатках (КТО).

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

Смотри Метод ортогональных базисов.

Перевод числа из СОК в обобщенную позиционную систему (ОПС)

Еще один метод определения величины числа связан с переводом числа из системы остаточных классов в ОПС. Для того, чтобы рассмотреть этот метод, выявим связь между представлением некоторого числа в этих двух системах.

Пусть по-прежнему СОК задается основаниями число в этой системе. И пусть – также основания ОПС, тогда число можно представить в виде

где – коэффициенты (цифры) ОПС.

Очевидно, что диапазоны чисел, представимых в СОК и ОПС совпадают, т.е. можно говорить о наличии взаимно однозначного соответствия между множеством представлений чисел в СОК и ОПС.

Это равенство можно переписать в следующем виде:

откуда следует, что цифры ОПС могут быть получены из соотношений:

Причем при определении цифр по формулам все вычисления можно вести в СОК.

Смотри Перевод числа из СОК в обобщенную позиционную систему.

Интервальные методы перевода

Достаточно эффективными методами перевода чисел из СОК в ПСС являются интервальные методы, основанные на интервальных характеристиках чисел. Одна из таких характеристик – номер интервала.

Смотри Интервальные методы перевода.

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

Расширение системы оснований является одной из основных немодульных операций в СОК. Выполнение этой операции бывает необходимо при выполнении операции деления чисел, при вычислении позиционных характеристик, при обнаружении переполнения при выполнении сложения или умножения чисел.

Задачу расширения системы оснований можно сформулировать следующим образом: найти остаточное представление числа по новому основанию (новым основаниям), если известно представление числа по другим основаниям остатки от деления на другие числа. Один из путей расширения системы оснований состоит в переводе числа в позиционную систему счисления и вычисления остатка от деления на новый модуль. Этот путь не является рациональным с точки зрения числа операций.

Другой метод расширения системы оснований позволяет определить цифру числа по новому основанию, базируясь на таких позиционных характеристиках числа, как ранг числа, след числа.

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