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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 5. Метод решета числового поля 172
однако, очевидно, одновременная вариация двух параметров дает большую
возможность в выборе хорошей полиномиальной пары. Этот вариант
построения полиномиальной пары получил развитие в более поздних
работах. Мы опишем вариант алгоритма построения полиномов f
1
и f
2
,
предложенный в 2006 г. Т. Кляйнъюнгом [29]:
1. Выбираем параметр m
2
, 1 ≤ m
2
n
1/d
.
В дальнейшем для совмещения обозначения со статьей Кляйнъюнга будем
использовать вместо m
2
обозначение p. Значение p выбирается равным
произведению нескольких небольших простых чисел p
i
, удовлетворяющих
условию p
i
≡ 1 ( mod d). Вместо m
1
будем писать просто m.
2. Выбираем старший коэффициент a
d
и m ≈ (n/a
d
)
1/d
так, чтобы
выполнялась конгруэнтность
a
d
· m
d
≡ n (mod p) (5.154)
Кляйнъюнг предлагает выбирать c
d
взаимно-простым с p, тогда уравнение
c
d
x
d
≡ n ( mod p) либо не имеет ни одного решения, либо имеет d решений.
3. Обозначим r
d
= n. Далее будем вычислять параметры r
i
, c
i
для
d > i ≥ 0 по реккурентным формулам:
r
i
=
r
i+1
− c
i+1
m
i+1
p
, c
i
=
r
i
m
i
+ δ
i
, (5.155)
где 0 ≤ δ
i
< p выбирается так, чтобы выполнить условие r
i
≡ c
i
m
i
(mod p).
Тогда, для всех i выполнится условие
r
i
=
i
X
j=0
c
j
m
j
p
i−j
, (5.156)
а при i = d выполнится r
d
= n = p
d
· f
1
(m/p) = F
1
(m, p).
Полином f
1
(x) оказывается определенным в этой конструкции,
а значение второго полинома f
2
(x) определяем равным px − m.
Полиномиальная пара определена. Этим заканчивается описание алгоритма
Кляйнъюнга.
Глава 5. Метод решета числового поля                                         172

однако, очевидно, одновременная вариация двух параметров дает большую
возможность в выборе хорошей полиномиальной пары. Этот вариант
построения полиномиальной пары получил развитие в более поздних
работах. Мы опишем вариант алгоритма построения полиномов f1 и f2 ,
предложенный в 2006 г. Т. Кляйнъюнгом [29]:

      1. Выбираем параметр m2 , 1 ≤ m2  n1/d .
В дальнейшем для совмещения обозначения со статьей Кляйнъюнга будем
использовать вместо m2 обозначение p. Значение p выбирается равным
произведению нескольких небольших простых чисел pi , удовлетворяющих
условию pi ≡ 1 ( mod d). Вместо m1 будем писать просто m.

      2. Выбираем старший коэффициент ad и m ≈ (n/ad )1/d так, чтобы
выполнялась конгруэнтность

                 ad · md ≡ n (mod p)                                      (5.154)

Кляйнъюнг предлагает выбирать cd взаимно-простым с p, тогда уравнение
cd xd ≡ n ( mod p) либо не имеет ни одного решения, либо имеет d решений.

      3. Обозначим rd = n. Далее будем вычислять параметры ri , ci для
d > i ≥ 0 по реккурентным формулам:

        ri+1 − ci+1 mi+1               ri
   ri =                  ,      ci =      + δi ,                          (5.155)
                p                      mi

где 0 ≤ δi < p выбирается так, чтобы выполнить условие ri ≡ ci mi (mod p).
Тогда, для всех i выполнится условие
                     i
                     X
              ri =         cj mj pi−j ,                                   (5.156)
                     j=0


а при i = d выполнится rd = n = pd · f1 (m/p) = F1 (m, p).
      Полином f1 (x) оказывается определенным в этой конструкции,
а значение второго полинома                f2 (x)   определяем равным   px − m.
Полиномиальная пара определена. Этим заканчивается описание алгоритма
Кляйнъюнга.

Страницы