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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 5. Метод решета числового поля 170
полиному f
1
(x) произвольной комбинации вида g(x) · f
2
(x), где степень
g(x) ≤ d − 1.
Выбор подходящих m и g(x) в базовом алгоритме GNFS можно
выполнить за сравнительно небольшое время в итерационной процедуре
(см.Murphy [41]). Этот выбор ограничен многочленами f
1
(x) и f
2
(x),
имеющими старший коэффициент, равный 1 (такие многочлены называются
унитарными).
Значительно больший набор возможностей появляется, если
рассматривать произвольные не унитарные многочлены f
1
(x) и f
2
(x).
Впервые возможность использования не унитарных полиномов описана в
статье 1993 г. Бухлера, Ленстры и Померанса [13], где были предложены
три возможных варианта расширения множества применяемых полиномов.
Опишем эти варианты:
1. Старший коэффициент c
d
полинома f
1
(x)–произвольное
целое число
Если взять равным, например, произведению небольших простых
сомножителей, то однородный многочлен F
1
(a, b) будем делиться на
p для каждого делителя p коэффициента c
d
и b, кратного p. Это
способствует увеличению количества гладких пар в области просеивания.
Проанализируем, что потребуется теперь изменить в наших формулах.
Пусть c
d
6= 1, и θ ∈ C–корень f
1
(x). Тогда β = c
d
·θ—алгебраическое
целое. Действительно, β —корень многочлена с целыми коэффициентами
H(x) = c
d−1
d
f
1
(x) = x
d
+ c
d−1
x
d−1
+ c
d
c
d−2
x
d−2
+ ... c
d−1
d
c
0
.
Отсюда, если S -множество пар (a, b) такое, что
Q
(a,b)∈S
(a − bθ)—квадрат в
Q(α) и S содержит четное число пар, тогда
(H
0
(c
d
θ))
2
·
Y
(a,b)∈S
(ac
d
− bc
d
θ)
является квадратом в Z[c
d
θ], например, γ
2
. Преобразуем множитель H
0
(c
d
x)
Глава 5. Метод решета числового поля                                                   170

полиному f1 (x) произвольной комбинации вида g(x) · f2 (x), где степень
g(x) ≤ d − 1.
      Выбор подходящих m и g(x) в базовом алгоритме GNFS можно
выполнить за сравнительно небольшое время в итерационной процедуре
(см.Murphy [41]). Этот выбор ограничен многочленами f1 (x) и f2 (x),
имеющими старший коэффициент, равный 1 (такие многочлены называются
унитарными).
      Значительно        больший            набор    возможностей        появляется,   если
рассматривать произвольные не унитарные многочлены f1 (x) и f2 (x).
Впервые возможность использования не унитарных полиномов описана в
статье 1993 г. Бухлера, Ленстры и Померанса [13], где были предложены
три возможных варианта расширения множества применяемых полиномов.
Опишем эти варианты:

       1. Старший коэффициент cd полинома f1 (x)–произвольное
целое число

       Если взять равным, например, произведению небольших простых
сомножителей, то однородный многочлен F1 (a, b) будем делиться на
p для каждого делителя p коэффициента cd и b, кратного p. Это
способствует увеличению количества гладких пар в области просеивания.
Проанализируем, что потребуется теперь изменить в наших формулах.

      Пусть cd 6= 1, и θ ∈ C–корень f1 (x). Тогда β = cd · θ —алгебраическое
целое. Действительно, β —корень многочлена с целыми коэффициентами

H(x) = cd−1         d
        d f1 (x) = x + cd−1 x
                              d−1
                                  + cd cd−2 xd−2 + ... cd−1
                                                        d   c0 .
                                                           Q
Отсюда, если S -множество пар (a, b) такое, что                (a,b)∈S   (a − bθ)—квадрат в
Q(α) и S содержит четное число пар, тогда
                                Y
             (H 0 (cd θ))2 ·             (acd − bcd θ)
                               (a,b)∈S


является квадратом в Z[cd θ], например, γ 2 . Преобразуем множитель H 0 (cd x)

Страницы