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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 5. Метод решета числового поля 165
Таким образом, число p = 9929 подходит для вычисления корня.
Таким же способом проверим еще два простых числа p = 9851 и p = 9907.
Примером того, что не каждое простое p удовлетворяет теореме 5.6,
является число p = 9923. Н.О.Д. (x
p
− x, h
p
(x)) = x − 847 6= 1.
2. Вычисление квадратного корня по алгоритму Шенкса-
Тоннелли
Во второй части алгоритма мы должны вычислить квадратные корни
из g
p
(x) = g(x) mod p для каждого простого p, отобранного в первой
части работы алгоритма (g(x) определен формулой 5.140). Приведем это
вычисления для p = 9929:
1. a(x) = g(x) mod 9929 = 2027x
2
+ 3891x + 6659.
2. Вычислим q = p
3
= 978 850 872 089. Разложим q − 1 в произведение
четного и нечетного чисел q −1 = 2
3
·122 356 359 011, откуда r = 3, s =
122 356 359 011. Используем такие же обозначения, как в (1.14).
3. Найдем квадратичный невычет в кольце многочленов по модулю g
p
(x)
с коэффициентами из Z/pZ . Таким невычетом является z(x) = x + 1.
Для проверки вычислим z(x)
(q−1)/2
(mod h
p
(x)) = 9928 ≡ −1 (mod p).
4. Вычислим y(x) = (x + 1)
s
(mod h
p
(x)) = 1273.
5. Вычислим λ
0
(x) = (a(x))
s
(mod h
p
(x)) =
= (2027x
2
+ 3891x + 6659)
122 356 359 011
(mod x
3
+ 15x
2
+ 29x + 8) =
= 9928 ≡ −1 (mod 9929).
6. Вычислим w
0
= (a(x))
(s+1)/2
=
= (2027x
2
+ 3891x + 6659)
61 178 179 506
(mod (x
3
+ 15x
2
+ 29x + 8)) =
= 2124x
2
+ 5715x + 4075.
7. Поскольку λ
2
0
≡ 1 (mod 9929), то порядок λ
0
равен 2, откуда m = 1.
Степень k = 2
d−m
= 4.
Глава 5. Метод решета числового поля                                          165

      Таким образом, число p = 9929 подходит для вычисления корня.
Таким же способом проверим еще два простых числа p = 9851 и p = 9907.
      Примером того, что не каждое простое p удовлетворяет теореме 5.6,
является число p = 9923. Н.О.Д. (xp − x, hp (x)) = x − 847 6= 1.

     2. Вычисление квадратного корня по алгоритму Шенкса-
Тоннелли

      Во второй части алгоритма мы должны вычислить квадратные корни
из gp (x) = g(x) mod p для каждого простого p, отобранного в первой
части работы алгоритма (g(x) определен формулой 5.140). Приведем это
вычисления для p = 9929:

  1. a(x) = g(x) mod 9929 = 2027x2 + 3891x + 6659.

  2. Вычислим q = p3 = 978 850 872 089. Разложим q − 1 в произведение
     четного и нечетного чисел q − 1 = 23 · 122 356 359 011, откуда r = 3, s =
     122 356 359 011. Используем такие же обозначения, как в (1.14).

  3. Найдем квадратичный невычет в кольце многочленов по модулю gp (x)
     с коэффициентами из Z/pZ . Таким невычетом является z(x) = x + 1.
     Для проверки вычислим z(x)(q−1)/2 (mod hp (x)) = 9928 ≡ −1 (mod p).

  4. Вычислим y(x) = (x + 1)s (mod hp (x)) = 1273.

  5. Вычислим λ0 (x) = (a(x))s (mod hp (x)) =

      = (2027x2 + 3891x + 6659)122 356 359 011 (mod x3 + 15x2 + 29x + 8) =
      = 9928 ≡ −1 (mod 9929).

  6. Вычислим w0 = (a(x))(s+1)/2 =

      = (2027x2 + 3891x + 6659)61 178 179 506 (mod (x3 + 15x2 + 29x + 8)) =
      = 2124x2 + 5715x + 4075.

  7. Поскольку λ20 ≡ 1 (mod 9929), то порядок λ0 равен 2, откуда m = 1.
     Степень k = 2d−m = 4.

Страницы