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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 5. Метод решета числового поля 171
в выражении для γ
2
(x):
H
0
(c
d
x) = c
d−1
d
·f
0
1
(x) = c
d−1
d
·F
0
1
(x, 1) =
1
c
d
·F
0
1
(x, c
d
) =
1
c
d
·
d−1
X
i=1
i·c
i
x
i
c
d−1−i
d
,
откуда выражение для многочлена γ
2
(θ) получит окончательный вид:
γ
2
(θ) =
1
c
2
d
·(F
0
1
(x, c
d
))
2
·
Y
(a,b)∈S
(ac
d
−bc
d
θ). (5.152)
Найдем целые коэффициенты многочлена γ(x) =
P
d−1
i−0
согласно
описанному раньше алгоритму вычислению квадратного корня, причем
базисом будет служить теперь множество {1, c
d
θ, ... (c
d
θ)
d−1
}. Замена θ
на c
d
m в многочлене g(x) позволяет найти делитель числа n также, как
и в случае унитарного многочлена f
1
(x). Ниже мы опишем необходимые
изменения в базовом алгоритме GNFS для наиболее общего варианта 3.
2. Замена условия f
1
(m) = n условием F
1
(m
1
, m
2
) = n
Поскольку f
1
(m
1
) = F
1
(m
1
, 1), то при m
2
= 1 этот вариант совпадает
со стандартным. Этот вариант дает возможность увеличить количество
допустимых полиномиальных пар, среди которых можно выбрать полиномы
с меньшими по модулю значениями коэффициентов. В статье [13] предложен
следующий вариант выбора m
1
, m
2
:
Полагаем c
d
= 1. Далее выберем m
1
≈ n
1/(d+1)
так, чтобы
разность n − m
d
1
имела делитель m
2
≈ n
1/(d+1)
, выполняя пробное деление
или факторизацию n − m
d
1
с помощью эллиптических кривых. Далее
раскладываем (n − m
d
1
)/m
2
по степеням m
1
, m
2
:
n − m
d
1
m
2
= c
d−1
m
d−1
1
+ ... + c
1
m
1
m
d−2
2
+ c
0
m
d−1
2
. (5.153)
3. Алгоритм Кляйнъюнга
В упомянутой статье [13] была упомянута возможность использования
общего варианта, при котором оба параметра c
d
не m
2
равны 1, но
было предложено никакого алгоритма для получения такого представления,
Глава 5. Метод решета числового поля                                                         171

в выражении для γ 2 (x):
                                                                        d−1
  0                                                 1 0            1 X
H (cd x) =    cdd−1 ·f10 (x)   =   cd−1 0
                                    d ·F1 (x, 1)   = ·F1 (x, cd ) = ·     i·ci xi cd−1−i
                                                                                   d     ,
                                                    cd             cd i=1

откуда выражение для многочлена γ 2 (θ) получит окончательный вид:

  2      1     0          2
                             Y
 γ (θ) = 2 · (F1 (x, cd )) ·   (acd − bcd θ).                                          (5.152)
        cd
                                    (a,b)∈S

                                                                              Pd−1
         Найдем целые коэффициенты многочлена γ(x) =                            i−0   согласно
описанному раньше алгоритму вычислению квадратного корня, причем
базисом будет служить теперь множество {1, cd θ, ... (cd θ)d−1 }. Замена θ
на cd m в многочлене g(x) позволяет найти делитель числа n также, как
и в случае унитарного многочлена f1 (x). Ниже мы опишем необходимые
изменения в базовом алгоритме GNFS для наиболее общего варианта 3.

         2. Замена условия f1 (m) = n условием F1 (m1 , m2 ) = n

         Поскольку f1 (m1 ) = F1 (m1 , 1), то при m2 = 1 этот вариант совпадает
со стандартным. Этот вариант дает возможность увеличить количество
допустимых полиномиальных пар, среди которых можно выбрать полиномы
с меньшими по модулю значениями коэффициентов. В статье [13] предложен
следующий вариант выбора m1 , m2 :

         Полагаем cd           = 1. Далее выберем m1                ≈ n1/(d+1) так, чтобы
разность n − md1 имела делитель m2 ≈ n1/(d+1) , выполняя пробное деление
или факторизацию n − md1 с помощью эллиптических кривых. Далее
раскладываем (n − md1 )/m2 по степеням m1 , m2 :

      n − md1
              = cd−1 md−1
                      1   + ... + c1 m1 m2d−2 + c0 md−1
                                                    2 .                                (5.153)
        m2

         3. Алгоритм Кляйнъюнга

         В упомянутой статье [13] была упомянута возможность использования
общего варианта, при котором оба параметра cd не m2 равны 1, но
было предложено никакого алгоритма для получения такого представления,

Страницы