ЮНИ-ЦЕНТР-XXI
Главная | Деятельность | Мероприятия | Школа юных | Работа с учителями |
Мероприятия » Семинар «Введение в теорию чисел и её приложения»

Приглашаем посетить семинар «Введение в теорию чисел и её приложения».

Семинар еженедельно проводится под руководством М.М.Васьковского, Н.В. Кондратенка и Н.П. Прохорова.

Первое заседание семинара – обзорная лекция произошло в среду 19 октября 2016 г.

Цели настоящего семинара – изложить основы теории чисел, необходимые для овладения современными наукоемкими информационными технологиями (в частности, в области защиты информации), а также познакомить участников семинара с новыми научными результатами, полученными руководителями семинара в области алгебраической, алгоритмической теории чисел и их приложений в криптографии и опубликованными в таких престижных научных журналах как Journal of Symbolic Computation, Journal Number Theory.

Приглашаются школьники, студенты, аспиранты,
а также все заинтересованные теорией чисел и её приложениями!


Предварительная программа семинара «Введение в теорию чисел и её приложения»

Часть 0. Вводная часть
0. Обзорная лекция, посвященная классическим и современным задачам теории чисел и их приложениям в информатике.

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

Часть 2. Введение в алгебраическую теорию чисел
7. Кольцо вычетов, мультипликативная группа вычетов. Алгебраические доказательства теоремы Эйлера, китайской теоремы об остатках, существования первообразных корней.
8. Алгебраические и трансцендентные числа. Теорема Лиувилля и конструктивное доказательство существования трансцендентных чисел.
9. Характеристики алгебраических чисел (степень, минимальный многочлен), приложения к доказательству Большой теоремы Ферма с рациональным показателем.
10. Определение квадратичных числовых полей. След и норма.
11. Арифметика кольца гауссовых чисел. Геометрическая интерпретация деления с остатком. Евклидовы квадратичные кольца и квадратичные кольца с единственной факторизацией.
12. Приложения цепных дробей к исследованию алгоритма Евклида в квадратичных кольцах и доказательству аналога теоремы Кронекера-Валена о кратчайшей длине алгоритма Евклида.
13. Строение простых чисел в квадратичных кольцах. Критерии простоты в квадратичных кольцах.

Часть 3. Прикладные задачи теории чисел
14. Понятие о криптографии с открытым ключом. Системы электронной цифровой подписи. RSA-криптосистема.
15. Свойства RSA-криптосистемы: сложность алгоритмов шифрования и дешифрования. Атака методом повторного шифрования и теорема Винера. Ограничения на выбор параметров. Аналоги RSA-криптосистемы в квадратичных кольцах с единственной факторизацией.
16. Криптосистемы Рабина и Эль-Гамаля.
17. Схемы разделения и верификации секрета (модулярная и полиномиальная).
18. Протоколы с нулевым разглашением (на примерах знания факторизации числа и дискретного логарифма).
19. Задача тестирования на простоту. Обзор классических и современных тестов на простоту (тесты на основе теоремы Ферма, Соловея-Штрассена, Миллера-Рабина). Их обобщения на квадратичные кольца с единственной факторизацией.
20. Задача факторизации. Обзор классических и современных методов факторизации (методы Ферма, цепных дробей и факторных баз, Полларда, идея метода решета числового поля).

Материалы лекций:
0. Обзорная лекция по теории чисел - Вводные сведения, касающиеся алгебраических чисел
1. Алгоритм Евклида и его сложность
2. Сравнения по модулю и их свойства. Теоремы Ферма и Эйлера

3. Квадратичные вычеты. Символы Лежандра и Якоби. Квадратичный закон взаимности
4. Показатели, первообразные корни...
5. Индексы и экспоненциальные сравнения
6. Полиномиальные сравнения и лемма Гензеля
7. Квадратичные сравнения
8. Цепные дроби
Решения задач первого семестра

Главная | Деятельность | Мероприятия | Школа юных | Работа с учителями |