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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 5. Метод решета числового поля 153
1. Ищем g(x) =Н.О.Д.(f
1
(x), x
p
− x). Целью этого шага является
отсечение части полинома f
1
(x), имеющей корни по модулю p. Например,
если окажется, что g(x) = 1, тогда f
1
(x) не имеет корней по модулю p.
2. По теореме 5.2 g(x − b) |x
p
− x и
x
p
− x = x(x
(p−1)/2
+ 1)(x
(p−1)/2
− 1) для любого b, 0 ≤ b < p (5.135)
3. Используя свойство 5.135 отделим корни g(x) mod p.
Рассмотрим этот алгоритм на примере многочлена f
1
(x) = x
3
+15x
2
+
29x + 8, p = 67:
1. Вычислим g(x) =Н.О.Д.(f
1
(x), x
p
− x) =Н.О.Д.(, x
6
7 − x) = x
3
+
15x
2
+ 29x + 8. Получили g(x) = f
1
(x), значит, f
1
(x) содержит все три
возможных корня f
1
(x) по модулю 67.
2. При b = 0 равенство (5.135) получит вид
g(x) = x
3
+15x
2
+29x+8 | x(x
33
+1)(x
33
−1)
Так как g(0) = 8 6= 0, x = 0 не является корнем g(x).
3. Вычислим Н.О.Д.(g(x), x
33
+x) = x
2
+21x+21, и Н.О.Д.(g(x), x
33
−
x) = x + 61, откуда найдем корень x = −61 ≡ 6 ( mod 67 ). Два оставшихся
корня являются корнями многочлена g
1
(x) = x
2
+ 21x + 21 ≡ x
2
+
21x − 46 ( mod 67 ). Их можно, например, вычисляя с помощью алгоритма
Шенкса–Тонелли квадратный корень из дискриминанта этого уравнения
D = (−21)
2
+ 4 · 46 = 2998 ≡ 50 ( mod 67 ).
Повторим это вычисление с другими значениями b. Подставляя в
равенство (5.135) b = 1, получим Н.О.Д.(g(x − 1), x
33
+ x) = g(x − 1) и
Н.О.Д.(g(x − 1), x
33
− x) = 1. Значит, расщепления g
1
(x
1
) не происходит и
b = 1 не решает нашей задачи.
Подставим b = 2. Получим Н.О.Д.(g(x − 2), x
33
+ x) = x + 21 и
Н.О.Д.(g(x−2), x
33
−x) = x+63, откуда x = −21 ≡ 46 ( mod 67 ), x = −63 ≡
6 ( mod 67 ). Числа x = 44 и x = 2 являются корнями f
1
(x) ( mod 67 ). Все
три корня найдены.
Глава 5. Метод решета числового поля                                     153

      1. Ищем g(x) =Н.О.Д.(f1 (x), xp − x). Целью этого шага является
отсечение части полинома f1 (x), имеющей корни по модулю p. Например,
если окажется, что g(x) = 1, тогда f1 (x) не имеет корней по модулю p.

      2. По теореме 5.2 g(x − b) | xp − x и

  xp − x = x(x(p−1)/2 + 1)(x(p−1)/2 − 1) для любого b, 0 ≤ b < p    (5.135)

      3. Используя свойство 5.135 отделим корни g(x) mod p.

      Рассмотрим этот алгоритм на примере многочлена f1 (x) = x3 + 15x2 +
29x + 8, p = 67:

      1. Вычислим g(x) =Н.О.Д.(f1 (x), xp − x) =Н.О.Д.(, x6 7 − x) = x3 +
15x2 + 29x + 8. Получили g(x) = f1 (x), значит, f1 (x) содержит все три
возможных корня f1 (x) по модулю 67.
      2. При b = 0 равенство (5.135) получит вид

g(x) = x3 +15x2 +29x+8 | x(x33 +1)(x33 −1)

Так как g(0) = 8 6= 0, x = 0 не является корнем g(x).
      3. Вычислим Н.О.Д.(g(x), x33 +x) = x2 +21x+21, и Н.О.Д.(g(x), x33 −
x) = x + 61, откуда найдем корень x = −61 ≡ 6 ( mod 67 ). Два оставшихся
корня являются корнями многочлена g1 (x) = x2 + 21x + 21 ≡ x2 +
21x − 46 ( mod 67 ). Их можно, например, вычисляя с помощью алгоритма
Шенкса–Тонелли квадратный корень из дискриминанта этого уравнения
D = (−21)2 + 4 · 46 = 2998 ≡ 50 ( mod 67 ).

      Повторим это вычисление с другими значениями b. Подставляя в
равенство (5.135) b = 1, получим Н.О.Д.(g(x − 1), x33 + x) = g(x − 1) и
Н.О.Д.(g(x − 1), x33 − x) = 1. Значит, расщепления g1 (x1 ) не происходит и
b = 1 не решает нашей задачи.
      Подставим b = 2. Получим Н.О.Д.(g(x − 2), x33 + x) = x + 21 и
Н.О.Д.(g(x−2), x33 −x) = x+63, откуда x = −21 ≡ 46 ( mod 67 ), x = −63 ≡
6 ( mod 67 ). Числа x = 44 и x = 2 являются корнями f1 (x) ( mod 67 ). Все
три корня найдены.

Страницы