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

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

Глава 5. Метод решета числового поля 169
гладких пар для составления системы линейных уравнений и время
вычисления квадратного корня из полинома в пространстве Z[x]/(f
1
(x)).
Все остальные составляющие алгоритма влияют значительно меньше на
производительность GNFS.
Приведем оценку метода решета числового поля, взятую из ([13]) на
основе функции L
n
(α; c), определенной на с.130. Эта оценка выполнена при
условии, что степень d и граница области просеивания y выбраны, как
указано ниже:
d =
3
1/3
+ o(1)
(log n/ log log n)
1/3
, n > d
2d
2
> 1,
u = y = L
n
1/3, (8/9)
1/3
+ o(1)
.
(5.150)
При выполнении условий (5.150) и времени вычисления корня (5.146)
время работы алгоритма решета числового поля оценивается величиной
T (n) = L
n
1/3, (64/9)
1/3
+ o(1).
(5.151)
Отметим, что приближенное значение константы (64/9)
1/3
равно
1, 92. Таким образом, уменьшение значения показателя степени в наиболее
важном сомножителе log n функции L
n
(α; c) от значения 1/2 в методе
квадратичного решета до 1/3 в методе решета числового поля дает тот
прогресс, который обеспечивает приоритет этого метода над методом
квадратичного решета и всеми остальными методами факторизации,
известными на сегодняшний день.
5.7. Улучшение алгоритма выбора полиномиальной
пары
Основную часть расчета в методе GNFS занимает процедура
просеивания. Эффективность этой процедуры зависит от величины
коэффициентов многочленов f
1
(x) и f
2
(x), а также наличия у них
корней по модулю небольших простых чисел. Множество подходящих
пар определяется путем вариации значения параметра m и добавления к
Глава 5. Метод решета числового поля                                 169

гладких пар для составления системы линейных уравнений и время
вычисления квадратного корня из полинома в пространстве Z[x]/(f1 (x)).
Все остальные составляющие алгоритма влияют значительно меньше на
производительность GNFS.
      Приведем оценку метода решета числового поля, взятую из ([13]) на
основе функции Ln (α; c), определенной на с.130. Эта оценка выполнена при
условии, что степень d и граница области просеивания y выбраны, как
указано ниже:
                                          2
d = 3 + o(1) (log n/ log log n)1/3 , n > d2d > 1,
      1/3


                                    
                         1/3
   u = y = Ln 1/3, (8/9)       + o(1) .
                                                                  (5.150)
      При выполнении условий (5.150) и времени вычисления корня (5.146)
время работы алгоритма решета числового поля оценивается величиной
                                   
                            1/3
      T (n) = Ln 1/3, (64/9) + o(1).                            (5.151)

      Отметим, что приближенное значение константы (64/9)1/3 равно
1, 92. Таким образом, уменьшение значения показателя степени в наиболее
важном сомножителе log n функции Ln (α; c) от значения 1/2 в методе
квадратичного решета до 1/3 в методе решета числового поля дает тот
прогресс, который обеспечивает приоритет этого метода над методом
квадратичного решета и всеми остальными методами факторизации,
известными на сегодняшний день.


5.7. Улучшение          алгоритма         выбора    полиномиальной
     пары
       Основную часть расчета в методе GNFS занимает процедура
просеивания. Эффективность этой процедуры зависит от величины
коэффициентов многочленов f1 (x) и f2 (x), а также наличия у них
корней по модулю небольших простых чисел. Множество подходящих
пар определяется путем вариации значения параметра m и добавления к

Страницы