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

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

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

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

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

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

от ____________________№_________ «____» ______________200__г.

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

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

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

 М. П.

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

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

 

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

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

___________________________ студентка 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.    Если  и  - произвольный многочлен с целыми коэффициентами, то .