Версия 13:48, 12 февраля 2015

Содержание

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).

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

Определение

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

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

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

Если $a$ и $p$ взаимно просты, то $a^{\varphi(p)} \equiv 1 \pmod p$ , где $\varphi(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$ легко реализуется преобразование и арифметические операции. Поэтому эффективно выбирать модули СОК в виде чисел Мерсенна и Ферма.

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

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

Определение системы остаточных классов

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

Смотри Система остаточных классов.

Выбор системы счисления

Под системой счисления понимают совокупность символический метод записи чисел, представление чисел с помощью письменных знаков, или, точнее, способ кодирования (представления) элементов некоторой конечной модели действительных чисел словами одного или более алфавитов.

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

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

Системы счисления подразделяются на позиционные, непозиционные и смешанные. (Система счисления)

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

Смешанная система счисления является обобщением b-ричной системы счисления и также зачастую относится к позиционным системам счисления. Смотри Полиадический код.

В непозиционных системах счисления величина, которую обозначает цифра, не зависит от её положения в числе. При этом система может накладывать ограничения на положение цифр.

Всякая вычислительная структура тесно связана с системой счисления, в которой она работает.

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

В качестве такой непозиционной системы удобна система остаточных классов.

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

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

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

Смотри Модульные операции.

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

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

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

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

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

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

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

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

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

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

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

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

Пусть по-прежнему СОК задается основаниями $p_1, p_2, \ldots, p_n$ и $A = ({\alpha}_1, {\alpha}_2, \ldots, {\alpha}_n)$ - число в этой системе. И пусть $p_1, p_2, \ldots, p_n$ являются также основаниями ОПС, тогда число $A$ можно представить в виде

$A = a_n\cdot p_1\cdot p_2\cdot \ldots \cdot p_{n-1} + a_{n-1}\cdot p_1\cdot p_2\cdot \ldots \cdot p_{n-2} + \ldots + a_3\cdot p_1\cdot p_2 + a_2\cdot p_1 + a_1$

где $0\le a_k<p_1\cdot p_2\cdot \ldots \cdot p_{k-1}$ – коэффициенты (цифры) ОПС.

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

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

$A = a_1 + p_1(a_2 + p_2(a_3 + \ldots +p_{n-2}(a_{n-1} + p_{n-1} a_n) \ldots ))$ ,

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

$a_1 = A - \left[ \frac{A}{p_1}\right] \cdot p_1 = A - A_1\cdot p_1$ , где $A_1 = \left[ \frac{A}{p_1}\right]$ ,

$a_2 = A_1 - \left[ \frac{A_1}{p_2}\right] \cdot p_2 = A_1 - A_2\cdot p_2$ , где $A_2 = \left[ \frac{A_1}{p_2}\right]$ ,

$\ldots$

$a_n = A_{n-1} - \left[ \frac{A_{n-1}}{p_n}\right] \cdot p_n = A_{n-1} - A_n\cdot p_n$ , где $A_n = \left[ \frac{A_{n-1}}{p_n}\right]$ .

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

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

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

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

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

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

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

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

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

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

Версия 13:13, 12 февраля 2015 (просмотреть исходный код) Isaeva (обсуждение \| вклад) ← Предыдущая правка		Версия 13:48, 12 февраля 2015 (просмотреть исходный код) Isaeva (обсуждение \| вклад) Следующая правка →
Строка 185:		Строка 185:


−	== Выбор системы ~~остаточных классов для представления чисел~~ ==	+	== Выбор системы счисления ==

	Под системой счисления понимают совокупность символический метод записи чисел, представление чисел с помощью письменных знаков, или, точнее, способ кодирования (представления) элементов некоторой конечной модели действительных чисел словами одного или более алфавитов.		Под системой счисления понимают совокупность символический метод записи чисел, представление чисел с помощью письменных знаков, или, точнее, способ кодирования (представления) элементов некоторой конечной модели действительных чисел словами одного или более алфавитов.

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

Версия 13:48, 12 февраля 2015

Содержание

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

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

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

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

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

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

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

Определение системы остаточных классов

Выбор системы счисления

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

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

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

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

Литература

Навигация

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

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

Варианты

Просмотры

Действия

Поиск

Навигация

Инструменты