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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 5. Метод решета числового поля 166
8. Вычислим λ
1
и w
1
:
λ
1
= λ
0
· y
k
(mod h
p
(x)) = 1
w
1
= w
0
· y
k−1
(mod h
p
(x)) = 6527x
2
+ 8769x + 6852.
Поскольку w
1
= 1, то вычисление закончено. Искомый корень из g
p
(x) =
2027x
2
+ 3891x + 6659 равен 6527x
2
+ 8769x + 6852.
Наконец последним шагом является вычисление корня x
p
= g
p
(x) mod
p = (2027 · 31
2
+ 3891 · 31 + 6659) mod 9929 = 5694.
3. Нахождение полного корня с помощью китайской теоремы
об остатков
В предыдущей секции был вычислен частичный квадратный корень из
произведения линейных многочленов a −bx для x ∈ M по модулю p = 9929
и найдено его значение при x = m.
Выполним такую же операцию по оставшимся модулям p = 9851
и p = 9907. Поскольку это вычисление полностью повторяет вычисление
предыдущей секции, мы его пропустим. Выпишем окончательные значения:
p g
p
(x) g
p
(m)
9851 7462x
2
+ 5679x + 4037 5694
9907 5126x
2
+ 5072x + 3125 4152
9929 3402x
2
+ 1160x + 3125 3077
Теперь надо вычислить полное значение корня g(m) mod n, используя
значения g(m) по частичным модулям 9851, 9907 и 9929. Иначе говоря, надо
решить систему сравнений:
x ≡ 5694 ( mod 9851 ),
x ≡ 4152 ( mod 9907 ),
x ≡ 3077 ( mod 9929 ).
Для решения этой задачи воспользуемся китайской теоремой об остатках
(разд. 1.15).
Глава 5. Метод решета числового поля                                    166

   8. Вычислим λ1 и w1 :

                λ1 = λ0 · y k (mod hp (x)) = 1
                w1 = w0 · y k−1 (mod hp (x)) = 6527x2 + 8769x + 6852.


Поскольку w1 = 1, то вычисление закончено. Искомый корень из gp (x) =
2027x2 + 3891x + 6659 равен 6527x2 + 8769x + 6852.
       Наконец последним шагом является вычисление корня xp = gp (x) mod
p = (2027 · 312 + 3891 · 31 + 6659) mod 9929 = 5694.

     3. Нахождение полного корня с помощью китайской теоремы
об остатков

      В предыдущей секции был вычислен частичный квадратный корень из
произведения линейных многочленов a − bx для x ∈ M по модулю p = 9929
и найдено его значение при x = m.
       Выполним такую же операцию по оставшимся модулям p = 9851
и p = 9907. Поскольку это вычисление полностью повторяет вычисление
предыдущей секции, мы его пропустим. Выпишем окончательные значения:

         p             gp (x)          gp (m)
       9851 7462x2 + 5679x + 4037 5694
       9907 5126x2 + 5072x + 3125 4152
       9929 3402x2 + 1160x + 3125 3077

       Теперь надо вычислить полное значение корня g(m) mod n, используя
значения g(m) по частичным модулям 9851, 9907 и 9929. Иначе говоря, надо
решить систему сравнений:
      
       x ≡ 5694 ( mod 9851 ),
      
      
          x ≡ 4152 ( mod 9907 ),
        
         x ≡ 3077 ( mod 9929 ).
        

Для решения этой задачи воспользуемся китайской теоремой об остатках
(разд. 1.15).

Страницы