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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 5. Метод решета числового поля 164
1. Выбор подходящих простых p
Первая часть алгоритма состоит в выборе подходящих p, для
которых многочлен g
p
(x) = f
1
(x) mod p = x
3
+ 15x
2
+ 29x + 8 mod p
является неприводимым в поле F
p
. Выберем значение p равным 9929. Для
проверки неприводимости полинома g
p
(x) воспользуемся следующими двумя
теоремами (напомним, что унитарным называется многочлен со старшим
коэффициентом равным 1):
Теорема 5.5. Пусть q = p
d
–положительная степень простого числа.
Многочлен
w
q
(x) = x
p
d
− x (5.144)
является произведением всех унитарных неприводимых многочленов над
Z/pZ , степень которых делит d.
Теорема 5.6. Пусть p–простое число. Многочлен f(x) степени d над
Z/pZ является неприводимым тогда и только тогда, когда выполнены
следующие два условия:
1. x
p
d
− x делится на f(x),
2. Н.О.Д.(x
p
d/p
i
− x, f(x)) = 1 для всех простых p
i
, делящих d.
1. Первым шагом алгоритма является вычисление h
p
(x) = f
1
(x) mod
p. В нашем примере, h
p
(x) совпадает с f
1
(x).
2. Проверим условие h
p
(x) | x
9929
3
− x. Это условие проверяется
непосредственным делением x
9929
3
− x на h
p
(x). Условие выполнено.
3. Проверим условие 2 теоремы 5.6 для единственного нетривиального
простого делителя p
1
= 3. Надо проверить, что Н.О.Д. (x
9929
, h
p
(x)) = 1.
Для этого вычислим
(x
9929
− x) mod h
p
(x) = 7449x
2
+ 4697x + 5984
и проверим, что Н.О.Д. (7449x
2
+ 4697x + 5984, x
3
+ 15x
2
+ 29x + 8) равен 1.
Глава 5. Метод решета числового поля                                         164

     1. Выбор подходящих простых p

       Первая часть алгоритма состоит в выборе подходящих p, для
которых многочлен gp (x) = f1 (x) mod p = x3 + 15x2 + 29x + 8 mod p
является неприводимым в поле Fp . Выберем значение p равным 9929. Для
проверки неприводимости полинома gp (x) воспользуемся следующими двумя
теоремами (напомним, что унитарным называется многочлен со старшим
коэффициентом равным 1):

Теорема 5.5. Пусть q = pd –положительная степень простого числа.
Многочлен
                   d
      wq (x) = xp − x                                                     (5.144)

является произведением всех унитарных неприводимых многочленов над
Z/pZ , степень которых делит d.

Теорема 5.6. Пусть p–простое число. Многочлен f (x) степени d над
Z/pZ является неприводимым тогда и только тогда, когда выполнены
следующие два условия:
        d
    1. xp − x делится на f (x),
                d/pi
    2. Н.О.Д.(xp       − x, f (x)) = 1 для всех простых pi , делящих d.


      1. Первым шагом алгоритма является вычисление hp (x) = f1 (x) mod
p. В нашем примере, hp (x) совпадает с f1 (x).
                                             3
      2. Проверим условие hp (x) | x9929 − x. Это условие проверяется
                                    3
непосредственным делением x9929 − x на hp (x). Условие выполнено.

      3. Проверим условие 2 теоремы 5.6 для единственного нетривиального
простого делителя p1 = 3. Надо проверить, что Н.О.Д. (x9929 , hp (x)) = 1.
Для этого вычислим

     (x9929 − x) mod hp (x) = 7449x2 + 4697x + 5984

и проверим, что Н.О.Д. (7449x2 + 4697x + 5984, x3 + 15x2 + 29x + 8) равен 1.

Страницы