Министерство образования Республики Беларусь

Белорусский государственный университет

Механико-математический факультет

Кафедра высшей алгебры
УТВЕРЖДАЮ

Проректор по учебной работе

________________________

Рег.№ __________________

«____» ______________ 2007 г.


Базовая учебная программа дисциплины
«Прикладные вопросы комбинаторики и теории чисел»

для студентов специальности 1-31 03 01-01«математика (научно-производственная деятельность)»

Минск

2007

Автор:
Каскевич В.И. — кандидат физико-математических наук, доцент кафедры высшей алгебры ММФ, БГУ

Рецензент:

Беняш-Кривец В.В. — доктор физико-математических наук, профессор кафедры высшей алгебры ММФ, БГУ

Одобрена на заседании кафедры

___________________________

протокол № 1 от 31 августа 2007 г.

Одобрена на заседании Ученого совета механико-математического факультета протокол № 1 от 18 сентября 2007 г.

Ответственный за редакцию: Каскевич Виктор Иванович

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

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

“ Прикладные вопросы комбинаторики и теории чисел ”

Цель курса “ Прикладные вопросы комбинаторики и теории чисел ”:

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

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

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


Тематический план курса “ Прикладные вопросы комбинаторики и

теории чисел ”

№ темы	Количество часов
Содержание курса	Лекции	Семинарские и практические
Раздел I. Комбинаторика
1. Комбинаторные конфигурации	4
2. Подстановки	2
3. Биномиальные коэффициенты	2
4. Разбиения множеств	2
5. Принцип включения и исключения	2
6. Формулы обращения	2
7. Производящие функции	2
Раздел II. Оценки сложности арифметических операций
8. Сложность операций с целыми числами	2
9. Сложность операций в кольце вычетов и модульная арифметика	2
10. Сложность операций в кольце многочленов	2
11. Дискретное преобразование Фурье	2
Раздел III. Прикладные вопросы и алгоритмы в теории чисел
12. Непрерывные дроби	2
13. Квадратичные вычеты	4
14. Распределение простых чисел	2
15. Проверка простоты	6
16. Построение больших простых чисел	4
17. Алгоритмы факторизации целых чисел	6
18. Криптосистема RSA	4
Всего аудиторных часов	52
ИТОГО:	52

Раздел I. КОМБИНАТОРИКА

Тема 1. Комбинаторные конфигурации

Введение. Комбинаторные задачи. Размещения с повторениями и размещения без повторений. Перестановки. Сочетания без повторений и сочетания с повторениями.

Тема 2. Подстановки
Группа подстановок. Теорема Кэли. Циклы и транспозиции. Инверсии. Алгоритм сортировки методом пузырька. Генерация перестановок. Сравнения и их свойства. Теоремы Ферма и Эйлера, функция Эйлера. Китайская теорема об остатках. Решение линейных сравнений от одной неизвестной и их систем.
Тема 3. Биномиальные коэффициенты
Элементарные тождества для биномиальных коэффициентов. Бином Ньютона. Свойства биномиальных коэффициентов. Треугольник Паскаля. Генерация подмножеств. Перестановки с повторениями. Формула k-нома (возведение суммы k слагаемых в степень)
Тема 4. Разбиения множеств
Разбиения множеств. Число Стирлинга 2 рода. Рекуррентные соотношения для подсчета. Число Стирлинга 1 рода. Число Белла.
Тема 5. Принцип включения и исключения
Объединение конфигураций. Принцип включения и исключения. Число булевых функций от n переменных. Число булевых функций, существенно зависящих от всех своих переменных.
Тема 6. Формулы обращения
Теорема обращения. Формулы обращения для биномиальных коэффициентов. Формулы для чисел Стирлинга.

Тема 7. Производящие функции

Понятие производящей функции. Метод неопределенных коэффициентов. Числа Фибоначчи и их производящая функция. Числа Каталана и их производящая функция.

Раздел II. ОЦЕНКИ СЛОЖНОСТИ АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ

Тема 8. Сложность операций с целыми числами

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

Тема 9. Сложность операций в кольце вычетов и модульная арифметика

Оценки сложности операций сложения, вычитания, умножения, обращения и деления в кольце вычетов. Понятие модульной арифметики. Оценка сложности прямого и обратного переходов к вычетам по взаимно простым модулям. Техника «разделяй и властвуй». Китайская теорема об остатках.

Тема 10. Сложность операций в кольце многочленов

Сложность операций с многочленами. Вычисление значения многочлена. Сложность алгоритма Руффини – Горнера.

Тема 11. Дискретное преобразование Фурье

Примитивные корни из 1. Дискретное преобразование Фурье и обратное дискретное преобразование Фурье. Алгоритм быстрого преобразования Фурье и его сложность. Применения дискретного преобразования Фурье при вычислениях в кольце чисел и кольце многочленов.

Раздел III. ПРИКЛАДНЫЕ ВОПРОСЫ И АЛГОРИТМЫ

В ТЕОРИИ ЧИСЕЛ

Тема 12. Непрерывные дроби
Алгоритм Евклида и непрерывные дроби. Теорема о фундаментальном соответствии. Подходящие дроби и их свойства. Представление рациональных и иррациональных чисел непрерывными дробями. Некоторые интересные свойства непрерывных дробей.

Тема 13. Квадратичные вычеты

Определение и свойства квадратичных вычетов. Символ Лежандра и его свойства. Квадратичный закон взаимности Гаусса. Символ Якоби и его свойства. Обобщенный квадратичный закон взаимности. Алгоритмы вычисления символа Лежандра.

Тема 14. Распределение простых чисел

Вопрос о распределении простых чисел и основные результаты. Теорема Чебышева о распределении простых чисел. Оценка величины n-го простого числа.

Тема 15. Проверка простоты
Решето Эратосфена. Критерий Вильсона. Тест на основе малой теоремы Ферма. Псевдопростые числа (числа Кармайкла) и их свойства. Обзор современных тестов распознавания простоты (тест Соловея – Штрассена, тест Рабина – Миллера, полиномиальный тест распознавания простоты).

Тема 16. Построение больших простых чисел

Критерий Люка. Числа Ферма. Терема Поклингтона и обобщение теоремы Люка. Теорема Диемитко. Метод Маурера. (n+1)-методы. Числа Мерсенна.

Тема 17. Алгоритмы факторизации целых чисел
Алгоритм пробных делений. Метод Полларда. Алгоритм Полларда – Штрассена. Факторизация Ферма. Обзор современных методов факторизации (алгоритм Диксона, алгоритм Брилхарда – Моррисона, метод квадратичного решета (p–1)-метод).

Тема 18. Криптосистема RSA

Общая схема работы криптосистемы RSA. Взаимосвязь между параметрами криптосистемы RSA. Условия на выбор параметров криптосистемы RSA.

ЛИТЕРАТУРА

ПО КУРСУ “ Прикладные вопросы комбинаторики и теории чисел ”
ОСНОВНАЯ:

1. 
   Новиков Ф.А. Дискретная математика для программистов. – Спб.: Питер, 2001.
   
2. 
   Черемушкин А.В. Лекции по арифметическим алгоритмам в криптографии. – М.: МЦНМО, 2002.
   

ДОПОЛНИТЕЛЬНАЯ:

1. 
   Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. М., “Мир”, 1987.
   
2. 
   Харин Ю.С., Берник В.И., Матвеев Г.В. Математические основы криптологии. Мн.: БГУ, 1999.
   
3. 
   Брюс Шнайер. Прикладная криптография. Протоколы, алгоритмы и исходные тексты на языке С. – Триумф, 2002.
   
4. 
   Ященко В.В. (общ.ред.) Введение в криптографию. – М: МЦНМО, "ЧеРо", 1999.
   
5. 
   Логачев О.А., Сальников А.А., Ященко В.В. Булевы функции в теории кодирования и криптологии. – М.: МЦНМО, 2004.
   
6. 
   Коблиц Н. Курс теории чисел и криптографии. – М: Научное изд-во ТВП, 2001.
   
7. 
   Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. – М: МЦНМО, 2003.
   
8. 
   Коутинхо С. Введение в теорию чисел. Алгоритм RSA. – М.: ПОСТМАРКЕТ, 2001.