Методы факторизации и дискретного логарифмирования



Скачать 62.22 Kb.
Дата03.06.2013
Размер62.22 Kb.
ТипПояснительная записка
Белорусский государственный университет


УТВЕРЖДАЮ

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

_____________________ Д.Г.Медведев

(подпись)

__________________________________

(дата утверждения)
Регистрационный № УД-______/баз.


МЕТОДЫ ФАКТОРИЗАЦИИ И ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ

Учебная программа для специальности

1-31 03 01 Математика (по направлениям)

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

2011 г.
Составители:

Васильев Денис Владимирович – доцент кафедры высшей алгебры механико-математического факультета Белорусского государственного университета, кандидат физико-математических наук


Рецензенты:

Калоша Николай Иванович – научный сотрудник отдела теории чисел Института математики НАН, кандидат физико-математических наук
РЕКОМЕНДОВАНА К УТВЕРЖДЕНИЮ:
Кафедрой высшей алгебры и защиты информации механико-математического факультета Белорусского государственного университета

(протокол №10 от 24.04.2011г.)

Учебно-методической комиссией механико-математического факультета Белорусского государственного университета

(протокол №8 от 16.05.2011г.)


Ответственный за выпуск: Д.В. Васильев

Ответственный за редакцию: Д.В. Васильев

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
В настоящее время теоретико-числовые алгоритмы повсеместно используются в различных системах обеспечения безопасности информации, таких как системы шифрования, цифровой подписи и обмена ключами. Предлагаемый курс посвящен рассмотрению вопросов связанных с разработкой и реализацией современных криптосистем с открытым ключом, использующих в своей работе методы теории чисел и алгебры. В рамках курса предполагается рассмотреть наиболее эффективные алгоритмы факторизации и дискретного логарифмирования, лежащие в основе современных криптосистем с открытым ключом. Учебный курс предназначен для студентов специальности 1-31 03 01-01 «математика (научно-производственная деятельность)». Для понимания курса необходимо знание основ теории чисел, базового курса алгебры и основ программирования ЭВМ.

Цель курса «Методы факторизации и дискретного логарифмирования» – изложить наиболее эффективные алгоритмы факторизации целых чисел и дискретного логарифмирования в циклических группах, которые лежат в основании современных систем шифрования с открытым ключом, цифровой подписи, распределения ключей.


При преподавании учебной дисциплины «Алгоритмы в теории чисел и криптографии» ставятся следующие задачи:

  • знакомство учащихся с теоретико-числовыми алгоритмами, использующимися в современных асимметрических криптосистемах электронной цифровой подписи, распределения ключей и шифрования;

  • развить алгоритмическое мышление и общую математическую культуру;

  • привить студентам умение самостоятельно изучать учебную и научную литературу в области математики.

Методика преподавания дисциплины строится на сочетании лекций (17 ч.) с семинарскими занятиями (17 ч.).

Примерный тематический план


Номер раздела, темы, занятия


Название раздела, темы, занятия; перечень изучаемых вопросов

Количество аудиторных часов

Материальное обеспечение занятия (наглядные пособия)

Литература

Форма контроля занятий

Лекции

Практические (семинарские) занятия

Лабораторные занятия

управляемая самостоятельная работа студента

1

2

3

4

5

6

7

8

9

1

Метод пробного деления. ρ-метод Полларда.

2

2










1-3




2

(p-1)-метод Полларда.

2

2










4




3

Метод Ленстры.

4

4










2-4




4

Методы решения разреженных систем линейных уравнений.

4

4










4




5

Метод квадратичного решета.

3

3










3-4




6

Метод решета числового поля.

2

2










3-4





Содержание учебного материала

Тема 1. Метод пробного деления. ρ-метод Полларда.

Решето Эратосфена. Метод пробных делений. Метод Ферма. ρ-метод Полларда. Алгоритм нахождения периода рекуррентной последовательности. Асимптотическая сложность ρ-метода Полларда.

Тема 2. (p-1)-метод Полларда.

Первая стадия (p-1)-метода Полларда. Вторая стадия (p-1)-метода Полларда. Оценка числа шагов в алгоритме (p-1)-метода Полларда.

Тема 3. Метод Ленстры.

Группа точек эллиптической кривой над простым конечным полем. Формула групповой операции на эллиптических кривых. Проективные и Якобиевы координаты.

Метод Ленстры. Оценка сложности метода Ленстры.
Тема 4. Методы решения разреженных систем линейных уравнений.

Метод структурированного Гауссового исключения. Метод градиентного спуска.

Метод Видемана. Метод Ланцоша

Тема 5. Метод квадратичного решета.

Алгоритм просеивания во множестве целых чисел. Метод квадратичного решета для задачи факторизации целых чисел. Метод MPQS.

Тема 6. Метод решета числового поля.

Стадия выбора многочленов для алгоритмов NFS. Рациональная и алгебраическая факторные базы. Алгоритм просеивания в кольце целых алгебраических чисел. Алгоритмы SNFS и GNFS.

ЛИТЕРАТУРА


  1. Харин Ю.С., Берник В.И. и Матвеев Г.В. Математические основы криптологии. — Мн., БГУ, 1999.

  2. Болотов А.А., Гашков С.Б., Фролов А.Б. и Часовских А.А. Элементарное введение в эллиптическую криптографию (в 2-х томах). — М., 2006.

  3. Нестеренко Ю.В. Теория чисел. — М., 2008

  4. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — М., 2003.







Похожие:

Методы факторизации и дискретного логарифмирования iconЗадача дискретного логарифмирования
В число таких задач входят соглашение о ключах Диффи-Хеллмана и его производных (§12. 6), шифрование Эль-Гамаля ( 4) и схема подписи...
Методы факторизации и дискретного логарифмирования iconФакторизация. Логарифмирование в конечных полях
Проблема факторизации – одна из старейших в теории чисел. Сложность самого быстрого алгоритма факторизации [Schn96]
Методы факторизации и дискретного логарифмирования iconПрограмма курса лекций (4 курс, 7 сем., 36 ч., экзамен)
Якоби, Зейделя и последовательной верхней релаксации; критерии и оценки скорости сходимости для модельной задачи уравнения Пуассона;...
Методы факторизации и дискретного логарифмирования iconНаправление 6 физика и математика
...
Методы факторизации и дискретного логарифмирования iconКомплексный анализ
Автор: д-р физ мат наук, профессор, зав кафедрой дискретного анализа Бондаренко В. А
Методы факторизации и дискретного логарифмирования iconМетодЫ решения оптимизационной задачи 2 Методы одномерной минимизации 2
«Методы оптимизации» и «Теория принятия решений». Каждый метод представлен в виде отдельной функции-члена класса. Все однотипные...
Методы факторизации и дискретного логарифмирования iconП. Ю. Поляков1, А. А. Фролов2, Д. Гусек
Предложен метод бинарной факторизации на основе сети Хопфилда. Метод применен для автоматической классификации статей конференций...
Методы факторизации и дискретного логарифмирования iconО факторизуемых группах
Вопросы, посвященные факторизации групп, в теории конечных групп занимают важное место. Под факторизацией конечной группы понимается...
Методы факторизации и дискретного логарифмирования iconВопрос ы к экзамену по курсу «Дискретные сигналы и системы»
Дискретизация аналоговых сигналов. Модулированная импульсная последовательность – модель дискретного сигнала
Методы факторизации и дискретного логарифмирования iconМетод Полларда Штрассена
Самым популярным среди алгоритмов факторизации целых чисел с экспоненциальной сложностью является метод Полларда Штрассена, имеющий...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org