Методы факторизации натуральных чисел. Ишмухаметов Ш.Т. - 4 стр.

  2.8. Факторизация с использованием квадратичных форм . . . . . . 75

3. Эллиптические кривые и их приложения в криптографии                         83
  3.1. Определение эллиптической кривой . . . . . . . . . . . . . . . . 84
  3.2. Число точек эллиптической кривой . . . . . . . . . . . . . . . . 87
  3.3. Алгоритм факторизации Ленстры . . . . . . . . . . . . . . . . . 89
  3.4. Криптографические протоколы на эллиптических кривых . . . 95
  3.5. Спаривание Вейля-Тейта . . . . . . . . . . . . . . . . . . . . . . 100
  3.6. Дивизоры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

4. Метод квадратичного решета                                                115
  4.1. Идея Мориса Крейтчика и алгоритм Диксона . . . . . . . . . . 115
  4.2. Метод Померанца . . . . . . . . . . . . . . . . . . . . . . . . . . 117
  4.3. Построение факторной базы . . . . . . . . . . . . . . . . . . . . 120
  4.4. Решение системы линейных уравнений . . . . . . . . . . . . . . 126
  4.5. Оценка сложности метода квадратичного решета           . . . . . . . . 127
  4.6. Пример факторизации методом квадратичного решета . . . . . 130
  4.7. Пример решения системы методом Гаусса . . . . . . . . . . . . . 134
  4.8. Вариация множителя в методе квадратичного решета . . . . . . 137
  4.9. Варианты метода квадратичного решета с возможностью
       распараллеливания . . . . . . . . . . . . . . . . . . . . . . . . . . 139
  4.10. Метод Занга (Zhang’ Special QS) . . . . . . . . . . . . . . . . . . 142

5. Метод решета числового поля                                               145
  5.1. Базовый алгоритм решета числового поля . . . . . . . . . . . . . 146
  5.2. Выбор факторных баз . . . . . . . . . . . . . . . . . . . . . . . . 151
  5.3. Просеивание в решете числового поля . . . . . . . . . . . . . . . 154
  5.4. Вычисление квадратного корня . . . . . . . . . . . . . . . . . . . 161
  5.5. Пример вычисления квадратного корня и оценка его сложности 163
  5.6. Оценка сложности решета числового поля          . . . . . . . . . . . . 168
  5.7. Улучшение алгоритма выбора полиномиальной пары . . . . . . 169
  5.8. Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175



                                       5