§2. Функция Эйлера.

Содержание

• Теоретико-числовые методы в криптографии
• Аннотация.
• Предисловие
• Введение
• Глава 1. Основы теории чисел. §1. Теория делимости.
• 1.1. Основные понятия и теоремы.
• 1.2. Наибольший общий делитель.
• 1.3 Нок (наименьшее общее кратное)
• 1.4. Простые числа
• Решето Эратосфена
• 1.5. Единственность разложения на простые сомножители.
• 1.6. Асимптотический закон распределения простых чисел.
• §2. Функция Эйлера.
• 2.1. Мультипликативные функции.
• 2.2. Функция Эйлера.
• §3. Теория сравнений
• 3.1. Свойства сравнений:
• 3.2. Полная система вычетов.
• 3.3. Приведенная система вычетов
• 3.4. Обратный элемент.
• 3.5. Алгебраические структуры на целых числах.
• 3.6. Теоремы Эйлера и Ферма. Тест Ферма на простоту.
• Тест Ферма на простоту
• 3.7. Применение теоремы Эйлера в rsa:
• §4. Сравнения с одним неизвестным
• 4.1. Сравнения первой степени.
• 4.2. Система сравнений первой степени. Китайская теорема об остатках.
• 4.3. Применения китайской теоремы об остатках.
• 4.4. Сравнения любой степени по простому модулю.
• 4.5. Сравнения любой степени по составному модулю.
• §5. Теория квадратичных вычетов
• 5.1. Квадратичные вычеты по простому модулю.
• 5.2. Символ Лежандра. Символ Якоби.
• Свойства символа Лежандра:
• Свойства символа Якоби:
• 5.3. Тест на простоту Соловея-Штрассена.
• Тест Соловея-Штрассена:
• 5.4. Решение квадратичных сравнений по простому модулю.
• 5.5. Квадратичные сравнения по составному модулю.
• 5.6. Тест на простоту Миллера-Рабина.
• 5.7. Связь задач извлечения квадратных корней и факторизации по модулю rsa. Криптосистема Рабина.
• 5.8. Квадраты и псевдоквадраты.
• 5.9. Числа Блюма.
• §6. Первообразные корни и индексы. Порождающий элемент и дискретный логарифм.
• 6.1. Основные понятия и теоремы.
• 6.2. Существование первообразных корней по модулю p.
• 6.3. Первообразные корни по модулям pα, 2pα.
• 6.4. Нахождение первообразных корней по простому модулю.
• 6.5. Существование и количество первообразных корней.
• 6.6. Дискретные логарифмы.
• 6.7. Проблема Диффи-Хеллмана.
• 6.8. Условная стойкость шифра Эль Гамаля.
• §7. Построение доказуемо простых чисел общего и специального вида.
• 7.1. Теорема Сэлфриджа и доказуемо простые числа общего вида на основании полного разложения (n—1).
• 7.2. Теорема Поклингтона и доказуемо простые числа общего вида на основании частичного разложения (n—1).
• 7.3. Числа Ферма. Теорема Пепина.
• 7.4. Числа Мерсенна.
• 7.5. Теорема Диемитко и процедура генерации простых чисел заданной длины гост р 34.10-94.
• Глава 2. Алгебраические основы теории чисел.
• §1. Основные понятия алгебры.
• 1.1. Начальные понятия.
• 1.2. Делимость в кольцах.
• 1.3. Деление с остатком.
• 1.4. Основная теорема арифметики.
• §2. Конечные поля и неприводимые многочлены.
• §3. Кольца многочленов.
• 3.1. Кольца многочленов.
• 3.2. Кольцо многочленов Zp[X].
• 3.3. Конечные поля многочленов.
• Глава 3. Алгоритмы в криптографии и криптоанализе. §1. Элементы теории сложности.
• §2. Алгоритмы факторизации.
• 2.1. Метод пробных делений.
• 2.2. Метод Ферма.
• 2.3. Метод квадратичного решета.
• 2.6. Методы случайных квадратов.
• §3. Алгоритмы дискретного логарифмирования.
• 3.1. Метод прямого поиска.
• 3.2. Шаг младенца – шаг великана.
• 3.4. Алгоритм Полига-Хеллмана.
• 3.5. Алгоритм исчисления порядка (index-calculus algorithm).
• Задачи и упражнения.
• Упражнения к Главе 2.
• Ответы к упражнениям.
• 1. Пояснительная записка
• 1.1. Цели и задачи дисциплины
• 1.2. Требования к уровню освоения содержания дисциплины
• 2. Объем дисциплины и виды учебной работы
• 3. Тематический план изучения дисциплины
• 4. Содержание разделов дисциплины
• 6. Вопросы к экзаменам
• 7.Литература основная:
• Дополнительная:
• Оглавление