Теоретико-числовые алгоритмы



Скачать 16.76 Kb.
Дата15.10.2012
Размер16.76 Kb.
ТипДокументы
ТЕОРЕТИКО-ЧИСЛОВЫЕ АЛГОРИТМЫ

чл.-корр. РАН Ю.В. Нестеренко

1 год

обязательный для специализации “Математические методы защиты информации”

1. Арифметическая сложность алгоритмов. Алгоритм Евклида, оценка его сложности (теорема Ламе). Квадратичные сравнения. Малая теорема Ферма. Символ Лежандра и его свойства. Вычисление символа Лежандра. Символ Якоби. Быстрый алгоритм для вычисления символа Якоби.

2. Быстрый алгоритм возведения в степень. Вычисление членов линейных рекуррентных последовательностей.

3. Вероятностные алгоритмы. Первообразные корни и их вычисление. Алгоритм Шенкса решения квадратичных сравнений и оценка его сложности при известном квадратичном невычете. Вероятностный алгоритм нахождения квадратичных невычетов.

4. Числа Кармайкла, псевдопростые числа. Простота чисел Ферма и Мерсенна. Вероятностные методы отсеивания составных чисел (тесты Миллера-Рабина, Соловея-Штрассена). Условный алгоритм Миллера для доказательства простоты чисел. Детерминированные -методы проверки простоты чисел. Построение больших простых чисел.

5. Алгоритм Адлемана-Ленстры-Коена доказательства простоты чисел.

6. Факторизация чисел с экспоненциальной сложностью: метод Ферма, алгоритмы Ленстры и Шермана-Лемана, -метод Полларда, -метод Полларда, алгоритм Полларда-Штрассена.

7. Субэкспоненциальные методы факторизации. Алгоритм Диксона, дополнительные стратегии. Алгоритм Бриллхарта-Моррисона. Квадратичное решето.

8. Решето числового поля на примере факторизации числа Ферма .

9. Алгоритмы дискретного логарифмирования по простому модулю: метод Гельфонда, алгоритм Поллига-Хеллмана, алгоритм Адлемана, алгоритм Копперсмитта-Одлыжко-Шреппеля.

10. Дискретное логарифмирование и решето числового поля.

11. Разложение многочленов на неприводимые множители над конечными полями: алгоритм Берлекэмпа, метод Кантора-Цассенхауза. Вероятностный алгоритм.

12. Решетки и их свойства. -алгоритм построения приведенного базиса решетки.

13. Факторизация многочленов в с полиномиальной сложностью.

14. Построение совместных рациональных приближений и нахождение минимумов квадратичных форм с помощью -алгоритма.

Похожие:

Теоретико-числовые алгоритмы iconЗанятие 5 Теоретико-числовые алгоритмы в криптографии
Цель. Изучение применяемых в криптографии базовых алгоритмов работы с большими числами
Теоретико-числовые алгоритмы iconТеоретико-числовые методы в криптографии
Автор: к ф м н., доцент, доцент кафедры алгебры и математической логики С. И. Яблокова
Теоретико-числовые алгоритмы iconПрограмма по дисциплине «Теоретико-числовые основы защиты информации» для специальности
Рабочая программа составлена на основании
Теоретико-числовые алгоритмы iconПрограмма курса лекций «теория чисел»
В настоящее время теоретико-числовые методы криптографии активно проникают в сферу экономики и финансов. Этому во многом способствует...
Теоретико-числовые алгоритмы iconТеоретико-графовые модели структуры фольклорных текстов, алгоритмы поиска закономерностей и их программная реализация
Специальность 05. 13. 18 – математическое моделирование, численные методы и комплексы программ
Теоретико-числовые алгоритмы icon§ теоретико-числовые свойства чисел фибоначчи
Если существует хотя бы одно число Фибоначчи un делящееся на m, то таких делящихся на m чисел Фибоначчи можно найти сколь угодно...
Теоретико-числовые алгоритмы icon§ теоретико-числовые свойства чисел фибоначчи
Если существует хотя бы одно число Фибоначчи un делящееся на m, то таких делящихся на m чисел Фибоначчи можно найти сколь угодно...
Теоретико-числовые алгоритмы iconРабочая программа по дисциплине «Теоретико-числовые методы в криптографии» для студентов специальности «Компьютерная безопасность»
Дисциплин как алгебра, теория чисел, теория сложности. Студентам, изучающим криптографию всерьез, необходимо знание ее математических...
Теоретико-числовые алгоритмы iconПрограмма по курсу «Теории чисел». Лектор: Иконникова Т. К. 3 курс 2006/2007 уч год
Теоретико-числовые функции. Целая и дробная части числа. Сумма и число делителей. Функция Мёбиуса. Функция Эйлера. Мультипликативность....
Теоретико-числовые алгоритмы iconЗанятие I тема. Разветвляющиеся алгоритмы. Оператор условия If
До сих пор Вы использовали линейные алгоритмы, т е алгоритмы, в которых все этапы решения задачи выполняются строго последовательно....
Разместите кнопку на своём сайте:
ru.convdocs.org


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