IV. Теоретические основы

• 10. Введение в теоретико-числовую и сложностную проблематику
• 11. Задача дискретного логарифмирования
  • 11.1 Введение
  • 11.2 Постановка задачи
  • 11.3 Логарифмирование в GF(q)*
    • 11.3.1 Алгоритм Гельфонда
    • 11.3.2 Алгоритм Полига - Хеллмана
    • 11.3.3 Логарифмирование в полях простого порядка
    • 11.3.4 Алгоритм Хеллмана - Рейнери
    • 11.3.5 Алгоритм Копперсмита
  • 11.4 Логарифмирование в Z_n*
  • 11.5 Рекомендуемая литература
  
  
• 12. Задача факторизации больших целых чисел
  • 12.1 Введение
  • 12.2 Факторизация чисел с экспоненциальной сложностью
    • 12.2.1 Алгоритм Шермана - Лемана
    • 12.2.2 Метод Полларда
    • 12.2.3 Метод Полларда - Штрассена
    • 12.2.4 Другие методы
  • 12.3 Факторизация чисел с субэкспоненциальной сложностью
    • 12.3.1 Алгоритм Диксона
    • 12.3.2 Методы ускорения алгоритма Диксона
    • 12.3.3 Алгоритм Бриллхарта - Моррисона
    • 12.3.4 Метод квадратичного решета
    • 12.3.5 Другие методы
  • 12.4 Метод решета числового поля
  
  
• 13. Методы построения больших простых чисел
  • 13.1 Введение
  • 13.2 Вероятностные тесты на простоту
  • 13.3 Простые числа специального вида
  • 13.4 Построение больших простых чисел n с использованием полного разложения n-1 на простые множители
  • 13.5 Построение больших простых чисел n с использованием частичного разложения n-1 на множители
  • 13.6 Полиномиальные алгоритмы доказательства простоты n с помощью известного полного разложения n-1 на простые множители
  • 13.7 Анализ алгоритма построения больших простых чисел, изложенного в Стандарте (ГОСТ Р 34.10-94) "Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма"
    • 13.7.1 Общетеоретические обоснования
    • 13.7.2 Алгоритм
    • 13.7.3 Всегда ли результатом работы Алгоритма являются простые числа?
    • 13.7.4 Распознает ли Алгоритм все простые числа?
    • 13.7.5 Отсеивание составных чисел
    • 13.7.6 Замечания
  • 13.8 Алгоритм построения простых чисел
  
  
• 14. Односторонние функции и псевдослучайные генераторы
  • 14.1 Односторонние функции
    • 14.1.1 Модели вычислений
    • 14.1.2 Односторонние функции в теории сложности
    • 14.1.3 Криптографические односторонние функции
    • 14.1.4 Гипотеза о существовании односторонних функций
    • 14.1.5 Функции с секретом
  • 14.2 Псевдослучайные генераторы
  
  
• 15. Основные понятия теории доказательств с нулевым разглашением
  • 15.1 Введение
  • 15.2 Интерактивные системы доказательства
  • 15.3 Интерактивные системы доказательства с нулевым разглашением