МІНІСТЕРСТВО ОСВІТИ І НАУКИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ
СТАВРОПОЛЬСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ
ФАКУЛЬТЕТ ФІЗИКО-МАТЕМАТИЧНИЙ
КАФЕДРА АЛГЕБРИ
Затверджена наказом по університету Допущена до захисту
від ____________________ № _________ В«____В» ______________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. Якщо і - Довільний многочлен з цілими коефіцієнтами, то.
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, ..., р ; повну систему найменших за абсолютною величиною відрахуван...
