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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

37
т.е. компоненты e
i
взаимно ортогональны по модулю m.
Алгоритм Гарнера
Для вычисления x может быть использован алгоритм Гарнера
(Garner’ algorithm), согласно которому x можно вычислить как n-й
член последовательности {x
i
}. Последовательности {x
i
}, {y
i
} строятся по
следующим формулам:
y
1
= x
1
= r
1
,
y
i+1
=
r
i+1
−x
i
m
1
·m
2
·...·m
i
mod m
i+1
,
x
i+1
= x
i
+ y
i+1
· m
1
· m
2
· ... · m
i
.
(1.16)
Достоинство этого алгоритма заключается в том, что вычисление каждого
последующей пары (x
i+1
, y
i+1
) использует только одно предыдущее значение
(x
i
, y
i
), что позволяет последовательно уточнять значения корня x.
Пример. Найти наименьшее положительное x, удовлетворяющее
системе уравнение:
x ≡ 2 ( mod 3 )
x ≡ 5 ( mod 7 )
x ≡ 4 ( mod 11 ).
Решение. В нашем примере m
1
= 2, m
2
= 7, m
3
= 11, r
1
= 2, r
2
=
5, r
3
= 4. Будем вычислять последовательно y
i
и x
i
, i = 1, 2, 3:
y
1
= x
1
= 2,
y
2
= (r
2
− x
1
) · (m
1
)
−1
mod m
2
= (5 − 2) · (3)
−1
mod 7 = 1
x
2
= x
1
+ (y
2
· m
1
mod m
2
) = 2 + (1 · 3 mod 7) = 5,
y
3
= (r
3
− x
2
) · (m
1
· m
2
)
−1
mod m
3
= (4 − 5) · 21
−1
mod 11 = 1,
x
3
= x
2
+ y
3
· m
1
· m
2
= 5 + 1 · 3 · 7 = 26.
Ответ: x = 26.
                                                                          37

т.е. компоненты ei взаимно ортогональны по модулю m.

Алгоритм Гарнера

       Для вычисления x может быть использован алгоритм Гарнера
(Garner’ algorithm), согласно которому x можно вычислить как n-й
член последовательности {xi }. Последовательности {xi }, {yi } строятся по
следующим формулам:
      
       y1 = x1 = r1 ,
      
      
                   i+1 −xi
        yi+1 = m1r·m 2 · ...· mi
                                 mod mi+1 ,                            (1.16)
      
       xi+1 = xi + yi+1 · m1 · m2 · ... · mi .
      

Достоинство этого алгоритма заключается в том, что вычисление каждого
последующей пары (xi+1 , yi+1 ) использует только одно предыдущее значение
(xi , yi ), что позволяет последовательно уточнять значения корня x.

       Пример. Найти наименьшее положительное x, удовлетворяющее
системе уравнение:
          
           x ≡ 2 ( mod 3 )
          
          
            x ≡ 5 ( mod 7 )
          
           x ≡ 4 ( mod 11 ).
          

       Решение. В нашем примере m1 = 2, m2 = 7, m3 = 11, r1 = 2, r2 =
5, r3 = 4. Будем вычислять последовательно yi и xi , i = 1, 2, 3:
  y1 = x1 = 2,
  y2 = (r2 − x1 ) · (m1 )−1 mod m2 = (5 − 2) · (3)−1 mod 7 = 1
  x2 = x1 + (y2 · m1 mod m2 ) = 2 + (1 · 3 mod 7) = 5,
  y3 = (r3 − x2 ) · (m1 · m2 )−1 mod m3 = (4 − 5) · 21−1 mod 11 = 1,
  x3 = x2 + y3 · m1 · m2 = 5 + 1 · 3 · 7 = 26.

Ответ: x = 26.

Страницы