![]() |
Начала теории чиселГ.И. Курбатова |
ПРЕДИСЛОВИЕ
В настоящем пособии излагается классический курс элементарной теории чисел, включающий в себя теорию делимости в кольце целых чисел и теорию сравнений, которая завершается в пособии теоремой Ферма (малой) и теоремой Эйлера.
Основной акцент делается на ясность изложения. Материал при этом расположен весьма наглядно, что улучшает восприятие текста. Приведено много полезных и разнообразных задач и упражнений, которые снабжены решениями. Для лучшего понимания доказательств в пособие включен небольшой раздел с элементами математической логики.
Имеется очень интересное и современное приложение классических результатов теории чисел (типа теоремы Эйлера) к криптографии -- так называемая "Схема алгоритма RSA", и, что очень важно, приводится математическое обоснование этого алгоритма.
Пособие несомненно будет полезно студентам математических факультетов, интересующимся компьютерными технологиями, а также школьникам старших классов физико-математических школ и лицеев.
Профессор
математико-механического
факультета СПбГУ
С.В. Востоков
ВВЕДЕНИЕ
Содержание учебного пособия составляет небольшую часть лекций и практических занятий по курсу "Высшая алгебра", которые автор читал в течение ряда лет на факультете прикладной математики - процессов управления Санкт-Петербургского государственного университета.
Пособие состоит из двух глав и приложения. Каждая глава завершается упражнениями и задачами, решения которых приведены в конце пособия. Это позволит начинающим познакомиться с приемами и формализмом доказательств.
В качестве иллюстрации необычайной востребованности теории чисел в современных прикладных задачах защиты информации рассмотрена система RSA шифрования с открытым ключом. Подробно излагается схема, математическое обоснование и алгоритм реализации системы RSA.
Учебное пособие не требует от читателя дополнительных знаний по алгебре, кроме обычного школьного курса. Оно может быть использовано также учителями и учащимися старших классов физико-математических школ и лицеев.
Автор искренне благодарен рецензентам - профессору математико-механического факультета СПбГУ С.В. Востокову и профессору факультета прикладной математики - процессов управления А.Ю. Утешеву - за внимательное прочтение рукописи и полезные замечания.
Большая благодарность И.И. Семеновой за помощь в оформлении рукописи.
ОГЛАВЛЕНИЕ
- ПРЕДИСЛОВИЕ
- ВВЕДЕНИЕ
- ГЛАВА 1. ТЕОРИЯ ДЕЛИМОСТИ В КОЛЬЦЕ ЦЕЛЫХ ЧИСЕЛ
- Свойства отношения делимости в кольце Z
- Деление с остатком в кольце целых чисел
- Наибольший общий делитель
- Свойства наибольшего общего делителя и взаимно простых чисел
- Алгоритм Эвклида
- Линейное представление наибольшего общего делителя
- Общий вид решения в целых числах уравнения ах + by =d
- Простые числа
- Решето Эратосфена
- Каноническое представление целых чисел
- Каноническое представление наибольшего общего делителя и наименьшего общего кратного, их связь ....
- Обобщение понятий наибольшего общего делителя, наименьшего общего кратного и взаимно простых чисел на п целых чисел
- ЗАДАЧИ К ГЛАВЕ 1
- ГЛАВА 2. СРАВНЕНИЯ В КОЛЬЦЕ ЦЕЛЫХ ЧИСЕЛ
- Свойства сравнений
- Доказательства свойств сравнений
- Классы вычетов по модулю m
- Полная и приведенная системы вычетов
- Функция Эйлера
- Теорема Эйлера и малая теорема Ферма
- ЗАДАЧИ К ГЛАВЕ 2
- ОБ ОДНОМ ПРИЛОЖЕНИИ ТЕОРИИ ЧИСЕЛ
- Схема алгоритма RSA
- Математическое обоснование
- Реализация алгоритма RSA
- ПРИЛОЖЕНИЕ А
- ПРИЛОЖЕНИЕ В
- ОТВЕТЫ, УКАЗАНИЯ, РЕШЕНИЯ
- Глава 1
- Глава 2
- ЛИТЕРАТУРА