Дипломная работа на тему "Математические основы системы остаточных классов"

ГлавнаяМатематика → Математические основы системы остаточных классов




Не нашли то, что вам нужно?
Посмотрите вашу тему в базе готовых дипломных и курсовых работ:

(Результаты откроются в новом окне)

Текст дипломной работы "Математические основы системы остаточных классов":


МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

СТАВРОПОЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ФИЗИКО-МАТЕМАТИЧЕСКИЙ

КАФЕДРА АЛГЕБРЫ

Утверждена приказом по университету Допущена к защите

от ____________________№_________ «____» ______________200__г.

Зав. кафедрой алгебры,

к. ф.-м. наук, доц. Копыткова

Людмила Борисовна

М. П.

ДИПЛОМНАЯ РАБОТА

Дипломный проект опубликован на сайте www.diplomnaya.sok olbank.ru

Новый банк готовых защищённых студентами дипломных проектов предлагает вам скачать любые проекты по нужной вам теме. Правильное выполнение дипломных проектов под заказ в Иркутске и в других городах России.

«МАТЕМАТИЧЕСКИЕ ОСНОВЫ СИСТЕМЫ ОСТАТОЧНЫХ КЛАССОВ»

Рецензенты: Выполнила:

___________________________ Пивоварова Елена Николаевна

___________________________ студентка 5 курса, гр. «Б»

специальности математика

очной формы обучения

Дата защиты: Научный руководитель:

«______» __________________ Копыткова Людмила Борисовна

к. ф.-м. н., доцент

Ставрополь, 2004 г.

Оглавление

Введение

Глава 1. Теоретико-числовая база построения СОК

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

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

§ 3. Китайская теорема об остатках и её роль в представлении чисел в СОК

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

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

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

§ 1. Представление числа в СОК. Модульные операции

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

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

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

Глава 3. Программная эммуляция алгоритмов перевода чисел из СОК в ПСС и обратно и алгоритма RSA

Цитированная литература

Введение

Инженеры и программисты, а также математики знакомы с таким понятием как цифровая обработка сигналов. Напомним некоторые факты.

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

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

Вообще, идею теории чисел для получения алгоритмов вычислений используют в 2-х наиболее важных направлениях обработки сигналов:

- в вычислении свёртки;

- в вычислении дискретного преобразования Фурье.

Цельже дипломной работы:

- установить взаимосвязь СОК и теории чисел;

- изучить СОК и методы перевода чисел из ПСС в СОК и обратно;

- разработать и выполнить программы на языке Paskal, содержащие различные методы перевода чисел из ПСС в СОК и обратно.

Дипломная работа состоит из введения, трёх глав и списка литературы.

Во введении даётся краткое обоснование поставленных задач.

Первая глава содержит известные факты теории чисел в той мере, в какой они будут применяться в дальнейшем. Здесь излагаются самые элементарные понятия теории чисел, в частности, сравнения и их свойства, различные теоремы. А также главная теорема в СОК – китайская теорема об остатках.

Вторая глава посвящена представлению чисел в СОК и различным методам перевода чисел из СОК в ПСС и от ПСС в СОК.

Третья глава содержит программные разработки методов перевода чисел из ПСС в СОК и обратно.

Глава 1. Теоретико-числовая база построения СОК

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

Возьмём произвольное фиксированное натуральное число p и будем рассматривать остатки при делении на р различных целых чисел.

При рассмотрении свойств этих остатков и проведении операций над ними удобно ввести понятие сравнения по модулю.

Определение. Целые числа а и b называются сравнимыми по модулю р, если разность чисел а – b делится на р, то есть, если Рисунок убран из работы и доступен только в оригинальном файле.. Соотношение между а, b и р запишем в виде:

Рисунок убран из работы и доступен только в оригинальном файле. (1.1)

запись mod p будет означать, что Рисунок убран из работы и доступен только в оригинальном файле., числа а и b – вычеты.

Если разность а – b не делится на р, то запишем:

Рисунок убран из работы и доступен только в оригинальном файле..

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

Примеры:

Рисунок убран из работы и доступен только в оригинальном файле., т. к. 101 – 17 = 84, а Рисунок убран из работы и доступен только в оригинальном файле. или Рисунок убран из работы и доступен только в оригинальном файле., т. к. числа 135 и 11 при делении на 4 дают остаток 3.

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

Определение: Целые числа а и b называются сравнимыми по модулю р, если остатки от деления этих чисел на р равны.

Дадим основные свойства сравнений:

1.  Рефлексивность отношения сравнимости:

Рисунок убран из работы и доступен только в оригинальном файле.

2.  Симметричность отношения сравнимости:

если, Рисунок убран из работы и доступен только в оригинальном файле., то Рисунок убран из работы и доступен только в оригинальном файле..

3.  Транзитивность отношения сравнимости:

если Рисунок убран из работы и доступен только в оригинальном файле., Рисунок убран из работы и доступен только в оригинальном файле., то Рисунок убран из работы и доступен только в оригинальном файле..

4.  Если Рисунок убран из работы и доступен только в оригинальном файле. и k – произвольное целое число, то Рисунок убран из работы и доступен только в оригинальном файле..

5.  Если Рисунок убран из работы и доступен только в оригинальном файле. и (k, p) = 1, то Рисунок убран из работы и доступен только в оригинальном файле..

6.  Если Рисунок убран из работы и доступен только в оригинальном файле. и k – произвольное натуральное число, то Рисунок убран из работы и доступен только в оригинальном файле..

7.  Если Рисунок убран из работы и доступен только в оригинальном файле., где k и р – произвольные натуральные числа, то Рисунок убран из работы и доступен только в оригинальном файле..

8.  Если Рисунок убран из работы и доступен только в оригинальном файле., Рисунок убран из работы и доступен только в оригинальном файле., то Рисунок убран из работы и доступен только в оригинальном файле. и Рисунок убран из работы и доступен только в оригинальном файле..

9.  Если Рисунок убран из работы и доступен только в оригинальном файле., Рисунок убран из работы и доступен только в оригинальном файле., то Рисунок убран из работы и доступен только в оригинальном файле..

10.  Если Рисунок убран из работы и доступен только в оригинальном файле., то при любом целом n > 0, Рисунок убран из работы и доступен только в оригинальном файле..

11.  Если Рисунок убран из работы и доступен только в оригинальном файле. и Рисунок убран из работы и доступен только в оригинальном файле. - произвольный многочлен с целыми коэффициентами, то Рисунок убран из работы и доступен только в оригинальном файле..

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

13.  Если Рисунок убран из работы и доступен только в оригинальном файле. и Рисунок убран из работы и доступен только в оригинальном файле., то Рисунок убран из работы и доступен только в оригинальном файле..

14.  Если Рисунок убран из работы и доступен только в оригинальном файле., то множество общих делителей а и р совпадает с множеством общих делителей b и р. В частности, Рисунок убран из работы и доступен только в оригинальном файле.

15.  Если Рисунок убран из работы и доступен только в оригинальном файле., Рисунок убран из работы и доступен только в оригинальном файле., …, Рисунок убран из работы и доступен только в оригинальном файле., то Рисунок убран из работы и доступен только в оригинальном файле., где Рисунок убран из работы и доступен только в оригинальном файле..

При делении целого числа на модуль р в остатке получается 0, 1, 2, 3,…, р – 1 чисел.

Отнесём все целые числа, дающие при делении на р один и тот же остаток в один класс, поэтому получится р – различных классов по модулю р.

В один класс попадут равноостаточные числа, они называются вычетами друг друга.

Обозначим через А0 – класс вычетов, которые при делении на р дают остаток 0.

Например, числа вида Рисунок убран из работы и доступен только в оригинальном файле..

Через А1 – числа, дающие при делении остаток 1.

Например, числа вида Рисунок убран из работы и доступен только в оригинальном файле..

Через А2 – числа, дающие при делении остаток 2.

Например, числа вида Рисунок убран из работы и доступен только в оригинальном файле..

Через Ар-1 – числа, дающие при делении остаток р – 1.

Например, числа вида Рисунок убран из работы и доступен только в оригинальном файле..

Полной системой вычетов по модулю р называется совокупность р-целых чисел, содержащая точно по одному представителю из каждого класса вычетов по модулю р. Каждый класс вычетов по модулю р содержит в точности одно из чисел совокупности всех возможных остатков от деления на р: 0, 1, …, р – 1. Множество {0, 1, …, р – 1} называется полной системой наименьших неотрицательных вычетов по модулю р. Можно легко доказать, что любая совокупность р чисел (р >1), попарно несравнимых по модулю р, есть полная система вычетов по модулю р. Часто рассматривают полную систему наименьших положительных вычетов: 1, 2, …, р; полную систему наименьших по абсолютной величине вычетов:

Рисунок убран из работы и доступен только в оригинальном файле. при чётном р и

Рисунок убран из работы и доступен только в оригинальном файле. при р нечётном.

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

Число классов, взаимно простых с модулем р, равно значению функции Эйлера φ(р).

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

Рассмотрим пример. Пусть р = 6.

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

Рисунок убран из работы и доступен только в оригинальном файле.r = 0;

Рисунок убран из работы и доступен только в оригинальном файле.r = 1;

Рисунок убран из работы и доступен только в оригинальном файле.r = 2;

Рисунок убран из работы и доступен только в оригинальном файле.r = 3;

Рисунок убран из работы и доступен только в оригинальном файле.r = 4;

Рисунок убран из работы и доступен только в оригинальном файле.r = 5;

где через r обозначен остаток от деления целого числа на 6.

Напомним теорему о делении с остатком:

Теорема: Разделить число Рисунок убран из работы и доступен только в оригинальном файле.на число Рисунок убран из работы и доступен только в оригинальном файле., Рисунок убран из работы и доступен только в оригинальном файле., с остатком, значит, найти пару целых чисел q и r, таких, что выполняются следующие условия: Рисунок убран из работы и доступен только в оригинальном файле..

Легко доказывается, что для любых целых чисел а и Рисунок убран из работы и доступен только в оригинальном файле.деление с остатком возможно и числа q и r определяются однозначно. В нашем примере полная система наименьших неотрицательных вычетов есть множество {0, 1, 2, 3, 4, 5}; полная система наименьших положительных вычетов – множество {0, 1, 2, 3, 4, 5, 6}; полная система наименьших по абсолютной величине вычетов – множество {-2,-1, 0, 1, 2, 3}; приведённая система вычетов – множество {1,5}, так как Рисунок убран из работы и доступен только в оригинальном файле.; фактор-множество Рисунок убран из работы и доступен только в оригинальном файле.

Один из методов выполнения арифметических операций над данными целыми числами основан на простых положениях теории чисел. Идея этого метода состоит в том, что целые числа представляются в одной из непозиционных систем – в системе остаточных классов. А именно: вместо операций над целыми числами оперируют с остатками от деления этих чисел на заранее выбранные простые числа – модули Рисунок убран из работы и доступен только в оригинальном файле.. Чаще всего числа Рисунок убран из работы и доступен только в оригинальном файле. выбирают из множества простых чисел.

Пусть Рисунок убран из работы и доступен только в оригинальном файле.Рисунок убран из работы и доступен только в оригинальном файле.…, Рисунок убран из работы и доступен только в оригинальном файле..

Так как в кольце целых чисел имеет место теорема о делении с остатком, т. е. Рисунок убран из работы и доступен только в оригинальном файле. где Рисунок убран из работы и доступен только в оригинальном файле., то кольцо Z, по определению, является евклидовым. Таким образом, в качестве чисел Рисунок убран из работы и доступен только в оригинальном файле. можно выбрать остатки от деления числа А на рi соответственно.

Рассмотрим гомоморфное отображение:

Рисунок убран из работы и доступен только в оригинальном файле..

Тогда каждому целому числу А можно поставить в соответствие кортеж Рисунок убран из работы и доступен только в оригинальном файле. наименьших неотрицательных вычетов по одному из соответствующих классов.

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

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

Действительно, пусть d – наименьшее целое положительное число вида Рисунок убран из работы и доступен только в оригинальном файле., например, Рисунок убран из работы и доступен только в оригинальном файле., где числа х0 и у0 не обязательно определены однозначно. Существование числа d следует только из принципа полной упорядоченности. Очевидно, что d > 0. Остаётся показать, что Рисунок убран из работы и доступен только в оригинальном файле.. Для этого надо проверить выполнение двух условий: а) Рисунок убран из работы и доступен только в оригинальном файле. и Рисунок убран из работы и доступен только в оригинальном файле.; б) если Рисунок убран из работы и доступен только в оригинальном файле. и Рисунок убран из работы и доступен только в оригинальном файле., то Рисунок убран из работы и доступен только в оригинальном файле.. Допустим, что свойство а) не выполняется и для определённости положим, что |Рисунок убран из работы и доступен только в оригинальном файле.. Тогда по теореме о делении с остатком Рисунок убран из работы и доступен только в оригинальном файле., и, следовательно,

Рисунок убран из работы и доступен только в оригинальном файле.,

что противоречит минимальности d. Выполнение свойства б) проверяется непосредственно:

Рисунок убран из работы и доступен только в оригинальном файле.Рисунок убран из работы и доступен только в оригинальном файле.Рисунок убран из работы и доступен только в оригинальном файле.

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

Рисунок убран из работы и доступен только в оригинальном файле. Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок убран из работы и доступен только в оригинальном файле. Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок убран из работы и доступен только в оригинальном файле. Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок убран из работы и доступен только в оригинальном файле. Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок убран из работы и доступен только в оригинальном файле. Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок убран из работы и доступен только в оригинальном файле. Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок убран из работы и доступен только в оригинальном файле. Рисунок убран из работы и доступен только в оригинальном файле.

В левом столбце алгоритма записана последовательность делений, которая получается в результате работы алгоритма Евклида и которая разрешена относительно остатков. Согласно теореме Ламе (1844 г.) число делений, которое необходимо выполнить для нахождения (а, b), не превосходит числа цифр в меньшем из чисел а и b, умноженного на 5 (оценка наихудшего случая для алгоритма Евклида). Теорема Ламе доказывается на основе последовательности Фибоначчи.

Там же доказывается, что время выполнения алгоритма Евклида оценивается равенством Рисунок убран из работы и доступен только в оригинальном файле., где L(a) и L(b) – число цифр в а и b соответственно. В правом столбце этого алгоритма каждый остаток выражен через Рисунок убран из работы и доступен только в оригинальном файле.. Надо вычислить Рисунок убран из работы и доступен только в оригинальном файле. и Рисунок убран из работы и доступен только в оригинальном файле.. Очевидно, что Рисунок убран из работы и доступен только в оригинальном файле. и Рисунок убран из работы и доступен только в оригинальном файле.. Сравнивая обе части на i-м шаге, получим

Рисунок убран из работы и доступен только в оригинальном файле.

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

Рисунок убран из работы и доступен только в оригинальном файле.: Рисунок убран из работы и доступен только в оригинальном файле. Рисунок убран из работы и доступен только в оригинальном файле.Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок убран из работы и доступен только в оригинальном файле.

Пример. Применим расширенный алгоритм Евклида к числам а = 342, b = 612. Весь алгоритм представим в виде следующей таблицы.

Расширенный алгоритм Евклида

--------------------------------------------------

Номер

итерации

|

q

|

A0

|

a1

|

x0

|

x1

|

Y0

|

y1

|
---------------------------------------------------------
0 | - | 342 | 612 | 1 | 0 | 0 | 1 |
---------------------------------------------------------
1 | 0 | 612 | 342 | 0 | 1 | 1 | 0 |
---------------------------------------------------------
2 | 1 | 342 | 270 | 1 | -1 | 0 | 1 |
---------------------------------------------------------
3 | 1 | 270 | 72 | -1 | 2 | 1 | -1 |
---------------------------------------------------------
4 | 3 | 72 | 54 | 2 | -7 | -1 | 4 |
---------------------------------------------------------
5 | 1 | 54 | 18 | -7 | 9 | 4 | -5 |
---------------------------------------------------------
6 | 3 | 18 | 0 | 9 | -34 | -5 | 19 |
--------------------------------------------------------- --------------------------------------------------

Заметим, что равенство Рисунок убран из работы и доступен только в оригинальном файле. выполняется на каждом шаге итерации. Алгоритм выдаёт d = 18, x = 9, y = -5 и тогда 18=342∙9 + 612∙(-5).

  § 3. Китайская теорема об остатках и её роль в представлении чисел в СОК

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

Теорема. Пусть Рисунок убран из работы и доступен только в оригинальном файле. - попарно взаимно-простые числа, больше 1, и пусть Рисунок убран из работы и доступен только в оригинальном файле.. Тогда существует единственное неотрицательное решение по модулю Р следующей системы сравнений:

Рисунок убран из работы и доступен только в оригинальном файле. Рисунок убран из работы и доступен только в оригинальном файле. …, Рисунок убран из работы и доступен только в оригинальном файле. (3.1)

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

Рисунок убран из работы и доступен только в оригинальном файле. колец Рисунок убран из работы и доступен только в оригинальном файле..

Существует много различных доказательств этой теоремы. Приведём конструктивное доказательство китайской теоремы об остатках.

Доказательство. Найдём число х, Рисунок убран из работы и доступен только в оригинальном файле., удовлетворяющее одновременно всем сравнениям, указанным в теореме. Систему сравнений будем решать присоединением на каждом шаге нового сравнения. Первое сравнение справедливо для всякого целого числа х вида Рисунок убран из работы и доступен только в оригинальном файле. где q1 – произвольное целое число. Для нахождения q1 подставим значение х во второе сравнение системы, после чего получим Рисунок убран из работы и доступен только в оригинальном файле. откуда Рисунок убран из работы и доступен только в оригинальном файле. где Рисунок убран из работы и доступен только в оригинальном файле. - обратный мультипликативный элемент к Рисунок убран из работы и доступен только в оригинальном файле. по модулю Рисунок убран из работы и доступен только в оригинальном файле.. Такой элемент существует, так как Рисунок убран из работы и доступен только в оригинальном файле. Найденное таким образом q1 можно записать в виде

Рисунок убран из работы и доступен только в оригинальном файле.

для некоторого целого числа Рисунок убран из работы и доступен только в оригинальном файле.. Подставив значение Рисунок убран из работы и доступен только в оригинальном файле. в выражение

Рисунок убран из работы и доступен только в оригинальном файле.

Теперь первые два сравнения могут быть заменены на одно

Рисунок убран из работы и доступен только в оригинальном файле. (3.2)

Применим теперь описанную процедуру к сравнению (3.2) и к одному из оставшихся сравнений системы (3.1). Повторяя этот процесс k – 1 раз, мы в конечном итоге найдём число х, удовлетворяющее всем сравнениям системы (3.1).

Докажем единственность решения системы (3.1). Воспользуемся методом от противного. Предположим, что существует другое решение Рисунок убран из работы и доступен только в оригинальном файле. системы (3.1). Тогда

Рисунок убран из работы и доступен только в оригинальном файле.

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

Пример. Решим систему сравнений

Рисунок убран из работы и доступен только в оригинальном файле.

Решение. Так как модули 13, 15, 19 попарно взаимно простые числа, то данная система имеет единственное решение по модулю Рисунок убран из работы и доступен только в оригинальном файле.. Сравнение Рисунок убран из работы и доступен только в оригинальном файле. соответствует диофантовому уравнению Рисунок убран из работы и доступен только в оригинальном файле., где Рисунок убран из работы и доступен только в оригинальном файле.. Заменяя х во втором сравнении системы на Рисунок убран из работы и доступен только в оригинальном файле., получаем Рисунок убран из работы и доступен только в оригинальном файле., т. е. Рисунок убран из работы и доступен только в оригинальном файле.. К числу 13 обратным мультипликативным элементом по модулю 15 является число 7. Умножая последнее сравнение на 7 и, переходя в нём к вычетам по модулю 15, получим Рисунок убран из работы и доступен только в оригинальном файле.. Таким образом, Рисунок убран из работы и доступен только в оригинальном файле.. Следовательно, Рисунок убран из работы и доступен только в оригинальном файле., при этом все числа вида Рисунок убран из работы и доступен только в оригинальном файле. являются решениями первых двух сравнений данной системы. Подставим в третье сравнение вместо х полученное выше значение Рисунок убран из работы и доступен только в оригинальном файле. или Рисунок убран из работы и доступен только в оригинальном файле.. Так как (5, 19) = 1, то Рисунок убран из работы и доступен только в оригинальном файле. или Рисунок убран из работы и доступен только в оригинальном файле.. Итак,

Рисунок убран из работы и доступен только в оригинальном файле., то есть х = 274.

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

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

Выход: х – единственное наименьшее неотрицательное решение системы по модулю Рисунок убран из работы и доступен только в оригинальном файле..

1.  Инициализация. Р:=1; х:=МОД(Рисунок убран из работы и доступен только в оригинальном файле.,Рисунок убран из работы и доступен только в оригинальном файле.) – подпрограмма нахождения остатка деления Рисунок убран из работы и доступен только в оригинальном файле. на Рисунок убран из работы и доступен только в оригинальном файле..

2.  Цикл для i от 1 до n – 1: Рисунок убран из работы и доступен только в оригинальном файле.MOДINV(p, Рисунок убран из работы и доступен только в оригинальном файле.);

q:=МОД(Рисунок убран из работы и доступен только в оригинальном файле.

3.  х:= х + pq, где MOДINV – подпрограмма вычисления мультипликативного обратного элемента.

4.  q:=МОД(Рисунок убран из работы и доступен только в оригинальном файле.

5.  Вернуть х.

Несложный анализ времени работы данного алгоритма показывает, что

Рисунок убран из работы и доступен только в оригинальном файле.

где Рисунок убран из работы и доступен только в оригинальном файле. - количество цифр числа Р, т. е. длина числа Р, при этом функция L ведёт себя как логарифм.

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

Вернёмся теперь к вопросу о мультипликативных обратных элементах в фактор-кольце Zp.

Теорема. Пусть Рисунок убран из работы и доступен только в оригинальном файле., тогда класс Рисунок убран из работы и доступен только в оригинальном файле. имеет мультипликативный обратный элемент по модулю р тогда и только тогда, когда (Рисунок убран из работы и доступен только в оригинальном файле., р) = 1.

Теорема. Характеристика λ конечного поля – простое число.

Рассмотрим два способа вычисления обратных мультипликативных элементов. Первый способ основан на рассмотренном выше алгоритме Евклида, второй – на теореме Эйлера.

Первый способ. Из условия (а, р) = 1 получаем ах + ру = 1 или Рисунок убран из работы и доступен только в оригинальном файле. и, следовательно, х – мультипликативный обратный к а по модулю р.

Второй способ. Предварительно напомним теорему Эйлера:

(а, р) = 1Рисунок убран из работы и доступен только в оригинальном файле.Рисунок убран из работы и доступен только в оригинальном файле., доказательство которой достаточно простое и мы его не приводим, так как его можно найти в любой книге по теории чисел. Частным случаем теоремы Эйлера является малая теорема Ферма.

Малая теорема Ферма. Если р – простое число и а – произвольное целое число, не делящееся на р, то Рисунок убран из работы и доступен только в оригинальном файле..

Следствие. В кольце Zp классов вычетов по модулю р из Рисунок убран из работы и доступен только в оригинальном файле. следует, что Рисунок убран из работы и доступен только в оригинальном файле.

Таким образом, для вычисления мультипликативного обратного к классу Рисунок убран из работы и доступен только в оригинальном файле. по модулю р в случае, когда Рисунок убран из работы и доступен только в оригинальном файле., достаточно Рисунок убран из работы и доступен только в оригинальном файле. возвести в степень k, где k = р – 2, если р – простое число, и Рисунок убран из работы и доступен только в оригинальном файле. в противном случае.

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

Из китайской теореме об остатках следует следующее

Утверждение. Пусть Рисунок убран из работы и доступен только в оригинальном файле. - каноническое представление числа р. Тогда функция, которая каждому классу Рисунок убран из работы и доступен только в оригинальном файле. ставит в соответствие кортеж Рисунок убран из работы и доступен только в оригинальном файле., где Рисунок убран из работы и доступен только в оригинальном файле. для Рисунок убран из работы и доступен только в оригинальном файле., является кольцевым изоморфизмом кольца Рисунок убран из работы и доступен только в оригинальном файле. класса вычетов по модулю р и кольца кортежей вида Рисунок убран из работы и доступен только в оригинальном файле., где Рисунок убран из работы и доступен только в оригинальном файле. для Рисунок убран из работы и доступен только в оригинальном файле.. Более того, если обозначить через * любую из кольцевых операций + или · , то

Рисунок убран из работы и доступен только в оригинальном файле.

Таким образом,

Рисунок убран из работы и доступен только в оригинальном файле.,

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

Рисунок убран из работы и доступен только в оригинальном файле..

Можно сделать вывод о том, что произвольное целое положительное число А, 0 < A < P, где Рисунок убран из работы и доступен только в оригинальном файле. и Рисунок убран из работы и доступен только в оригинальном файле. для Рисунок убран из работы и доступен только в оригинальном файле., однозначно представимо своими наименьшими неотрицательными остатками по модулю Рисунок убран из работы и доступен только в оригинальном файле., причём сложение (а, следовательно, и вычитание) и умножение выполняются покомпонентно.

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

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

При рассмотрении отдельных классов простых чисел значительный интерес представляет вопрос о простых числах вида Рисунок убран из работы и доступен только в оригинальном файле., где m – нечётное, именуемые числами Мерсенна. При простых значениях m = p число Рисунок убран из работы и доступен только в оригинальном файле. может оказаться простым, но может быть составным.

Например, при р = 2, 3, 5, 7, 13, 17, 19 мы получаем простые числа Мерсенна: 3, 7, 31, 127, 8191, 131071, а при р = 11, 23, 29 числа Рисунок убран из работы и доступен только в оригинальном файле. - составные.

Числа вида Рисунок убран из работы и доступен только в оригинальном файле., где k – положительное, обычно называют числами Ферма. При k = 0, 1, 2, 3, 4 числа Ферма простые: 3, 5, 17, 257, 65537. Все остальные числа Ферма – составные. Все числа Мерсенна и Ферма – взаимно простые.

Необходимо отметить, что значения чисел Мерсенна и Ферма быстро растут. Это не позволяет использовать лишь их в качестве модуле СОК.

При работе же на двоичных компьютерах, иногда желательно выбирать модули Рисунок убран из работы и доступен только в оригинальном файле. в виде чисел Мерсенна

Рисунок убран из работы и доступен только в оригинальном файле.. (5.1)

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

Рисунок убран из работы и доступен только в оригинальном файле., Рисунок убран из работы и доступен только в оригинальном файле.. (5.2)

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

Рисунок убран из работы и доступен только в оригинальном файле.,

Рисунок убран из работы и доступен только в оригинальном файле..

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

Рисунок убран из работы и доступен только в оригинальном файле..

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

Рисунок убран из работы и доступен только в оригинальном файле.. (5.3)

Формула (5.3) утверждает, в частности, что

Рисунок убран из работы и доступен только в оригинальном файле..

Уравнение (5.3) следует из алгоритма Евклида и тождества

Рисунок убран из работы и доступен только в оригинальном файле.,

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

Рисунок убран из работы и доступен только в оригинальном файле., Рисунок убран из работы и доступен только в оригинальном файле.,Рисунок убран из работы и доступен только в оригинальном файле., Рисунок убран из работы и доступен только в оригинальном файле., Рисунок убран из работы и доступен только в оригинальном файле.,

что обеспечивает эффект

Здесь опубликована для ознакомления часть дипломной работы "Математические основы системы остаточных классов". Эта работа найдена в открытых источниках Интернет. А это значит, что если попытаться её защитить, то она 100% не пройдёт проверку российских ВУЗов на плагиат и её не примет ваш руководитель дипломной работы!
Если у вас нет возможности самостоятельно написать дипломную - закажите её написание опытному автору»


Просмотров: 547

Другие дипломные работы по специальности "Математика":

Интеграл Лебега-Стилтьеса

Смотреть работу >>

Расширение кольца с помощью полутела

Смотреть работу >>

Качественное исследование в целом двумерной квадратичной стационарной системы с двумя частными интегралами в виде кривых второго и первого порядков

Смотреть работу >>

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

Смотреть работу >>

Кольцо целых чисел Гаусса

Смотреть работу >>