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

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

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

Определение

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

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

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

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

Всякая вычислительная структура тесно связана с системой счисления, в которой она работает. Под системой счисления понимают совокупность приёмов обозначения (записи) чисел, или, точнее, способ кодирования (представления) элементов некоторой конечной модели действительных чисел словами одного или более алфавитов. Кодирование представляет собой инъективное отображение диапазона системы счисления на декартово произведение его алфавитов, т. е. $F:D\mapsto A$, где $A = A_1 \times A_2 \times \ldots \times A_n$.

Иначе говоря, отображение $F$ элементу $x\in D$ ставит в соответствие кодовое слово $(x_1, x_2, \ldots , x_n)$, где $x_i = A_i (i=1,\ldots,n)$ - $i$-я цифра, $n$ – длина кода.

С помощью обратного отображения $F^{-1}$, которое называют декодированием, можно определить систему счисления.

К любой кодовой системе применимы следующие требования:

• возможность представления в данной системе любой величины в рассматриваемом, заранее назначенном диапазоне;
• единственность представления – любая кодовая комбинация соответствует одному и только одному числу в заданном диапазоне;
• простота оперирования числами в данной системе счисления.

Таким образом, коды чисел являются именами числовых объектов, составляющих числовой диапазон. Диапазоны как модели вещественных чисел должны с максимально доступной полнотой и простотой отражать свойства числового множества. Всякое представление чисел рабочего диапазона является лишь составным элементом соответствующей машинной арифметики и не может рассматриваться отдельно от неё. Арифметические свойства той или иной системы счисления прежде всего определяются характером межразрядных связей, появляющихся в ходе выполнения операций над кодовыми словами. Исследования показали, что в рамках обычной позиционной системы счисления (ПСС) значительного ускорения выполнения операций добиться невозможно. Это объясняется тем, что в ПСС значение разряда любого числа, кроме младшего, являющегося результатом двухместной арифметической операции, зависит не только от значения одноимённых операндов, но и от всех младших разрядов, т. е. ПСС обладает строго последовательной структурой. Сегодня, предпочтение отдаётся вычислительным структурам, обладающими способностями к параллельной обработке информации. Этими особенностями обладают непозиционные коды с параллельной структурой, которые позволяют реализовать идею распараллеливания операций на уровне выполнения элементарных арифметических действий.

Представление чисел в виде набора остатков от деления на выбранные натуральные модули - основания системы называется системой остаточных классов - СОК (residue number system - RNS) или модулярной системой счисления - МСС (modular system).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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