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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 5. Метод решета числового поля 163
неприводим. Для такого случая метод Ковейна также не будет работать. В
статье Бухлера, Ленстры и Померанса [13] приведены возможные варианты
вычисления корня в этом случае.
Вычисление корня методом подъема Гензеля
Идея подъема Гензеля (Hensel’s Lifting) уже использовалась в нашей книге
при построении факторной базы в методе квадратичного решета для
вычисления корней полинома просеивания q(x) по степени p
k+1
, если корни
q(x) ≡ 0 ( mod p
k
) известны.
Первоначально выбирается простой модуль p, для которого многочлен
g(x) mod p является неприводимым. Так же, как и в методе Ковейна,
сначала вычисляется корень α
1
(x) из q(x) (modp ). Предположим, что
найден корень α
k
(x) из q(x) ( modp
k
) и требуется найти корень α
k+1
(x) по
модулю p
k+1
. Коэффициенты α
k+1
(x) сравнимы с коэффициентами α
k
(x) по
модулю p
k
. Отсюда, каждый коэффициент a
i
, k + 1 имеет вид a
i
, k + 1+t
i
·p,
где t
i
–целое число из интервала [0; p − 1]. Подставляя выражения для
всех a
i
, k + 1 в уравнение α
2
k+1
(x) = g(x) mod p
k+1
, получим уравнения,
позволяющие найти все значения t
i
, а зная их, вычислить коэффициенты
многочлена α
k+1
(x). Этот метод применим для любой степени многочлена
f
1
(x), однако при увеличении степени k коэффициенты α
k
(x) достигают
огромных значений, что делает вычисления новых полиномов α
k+1
(x) очень
трудоемким.
5.5. Пример вычисления квадратного корня и оценка его
сложности
В этом разделе рассмотрим пример вычисления корня из многочлена
5.140, определенного ранее для n = 45113, методом редукции к конечным
подполям. Этот алгоритм состоит из трех основных шагов.
Глава 5. Метод решета числового поля                                     163

неприводим. Для такого случая метод Ковейна также не будет работать. В
статье Бухлера, Ленстры и Померанса [13] приведены возможные варианты
вычисления корня в этом случае.

Вычисление корня методом подъема Гензеля

Идея подъема Гензеля (Hensel’s Lifting) уже использовалась в нашей книге
при построении факторной базы в методе квадратичного решета для
вычисления корней полинома просеивания q(x) по степени pk+1 , если корни
q(x) ≡ 0 ( mod pk ) известны.
      Первоначально выбирается простой модуль p, для которого многочлен
g(x) mod p является неприводимым. Так же, как и в методе Ковейна,
сначала вычисляется корень α1 (x) из q(x) (modp ). Предположим, что
найден корень αk (x) из q(x) ( modpk ) и требуется найти корень αk+1 (x) по
модулю pk+1 . Коэффициенты αk+1 (x) сравнимы с коэффициентами αk (x) по
модулю pk . Отсюда, каждый коэффициент ai , k + 1 имеет вид ai , k + 1+ti ·p,
где ti –целое число из интервала [0; p − 1]. Подставляя выражения для
                             2
всех ai , k + 1 в уравнение αk+1 (x) = g(x) mod pk+1 , получим уравнения,
позволяющие найти все значения ti , а зная их, вычислить коэффициенты
многочлена αk+1 (x). Этот метод применим для любой степени многочлена
f1 (x), однако при увеличении степени k коэффициенты αk (x) достигают
огромных значений, что делает вычисления новых полиномов αk+1 (x) очень
трудоемким.


5.5. Пример вычисления квадратного корня и оценка его
      сложности
      В этом разделе рассмотрим пример вычисления корня из многочлена
5.140, определенного ранее для n = 45113, методом редукции к конечным
подполям. Этот алгоритм состоит из трех основных шагов.

Страницы