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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 5. Метод решета числового поля 147
разделах:
1. Выберем степень неприводимого многочлена d ≥ 3 (можно взять
d = 2, но в этом случае никакого выигрыша по отношению к методу
квадратичного решета не будет).
2. Выберем целое число m, bn
1/(d+1)
c < m < bn
1/d
c, и разложим n по
основанию m:
n = m
d
+ a
d−1
m
d−1
+ ... + a
0
. (5.128)
Отметим, что в базовой версии алгоритма старший коэффициент
многочлена f
1
(x) всегда равен 1, однако, на с. 169 мы обсудим, как
использовать многочлены с произвольным старшим коэффициентом.
3. С разложением (5.128) свяжем неприводимый в кольце Z[x] (кольцо
полиномов от переменной x с целыми коэффициентами) полином
f
1
(x) = x
d
+ a
d−1
x
d−1
+ ... + a
0
. (5.129)
4. Определим полином просеивания F
1
(a, b) как однородный полином от
двух переменных a и b:
F
1
(a, b) = b
d
·f
1
(a/b) = a
d
+a
d−1
a
d−1
b+a
d−2
a
d−1
b
2
+ ... +a
0
b
d
. (5.130)
Забегая вперед, скажем, что значение F
1
(a, b) равно норме полинома
a − bx в алгебраическом числовом поле Q[θ], полученном добавление
к полю рациональных чисел Q в общем случае комплексного корня
θ многочлена f
1
(x) (см.стр. 184). Свойство коммутативности нормы
Nr(h
1
(x)·h
2
(x)) = (Nr(h
1
(x))·Nr(h
2
(x)) позволяет вместо разложения
многочленов из кольца Z[θ] выполнять разложение их норм.
5. Также определим второй многочлен f
2
(x) = x −m и соответствующий
однородный многочлен F
2
(a, b) = a −bm. Главное требование к выбору
пары (f
1
, f
2
) состоит в том, что должно выполняться условие:
f
1
(m) ≡ f
2
(m) ( mod n ), (5.131)
Глава 5. Метод решета числового поля                                              147

разделах:

  1. Выберем степень неприводимого многочлена d ≥ 3 (можно взять
     d = 2, но в этом случае никакого выигрыша по отношению к методу
     квадратичного решета не будет).

  2. Выберем целое число m, bn1/(d+1) c < m < bn1/d c, и разложим n по
     основанию m:

      n = md + ad−1 md−1 + ... + a0 .                                          (5.128)

     Отметим, что в базовой версии алгоритма старший коэффициент
     многочлена f1 (x) всегда равен 1, однако, на с. 169 мы обсудим, как
     использовать многочлены с произвольным старшим коэффициентом.

  3. С разложением (5.128) свяжем неприводимый в кольце Z[x] (кольцо
     полиномов от переменной x с целыми коэффициентами) полином

       f1 (x) = xd + ad−1 xd−1 + ... + a0 .                                    (5.129)

  4. Определим полином просеивания F1 (a, b) как однородный полином от
     двух переменных a и b:

      F1 (a, b) = bd ·f1 (a/b) = ad +ad−1 ad−1 b+ad−2 ad−1 b2 + ... +a0 bd .   (5.130)

     Забегая вперед, скажем, что значение F1 (a, b) равно норме полинома
     a − bx в алгебраическом числовом поле Q[θ], полученном добавление
     к полю рациональных чисел Q в общем случае комплексного корня
     θ многочлена f1 (x) (см.стр. 184). Свойство коммутативности нормы
     N r(h1 (x)·h2 (x)) = (N r(h1 (x))·N r(h2 (x)) позволяет вместо разложения
     многочленов из кольца Z[θ] выполнять разложение их норм.

  5. Также определим второй многочлен f2 (x) = x − m и соответствующий
     однородный многочлен F2 (a, b) = a − bm. Главное требование к выбору
     пары (f1 , f2 ) состоит в том, что должно выполняться условие:

      f1 (m) ≡ f2 (m) ( mod n ),                                               (5.131)

Страницы