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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

44
всех 1 ≤ i ≤ n. Более того, любые два таких числа x
1
и x
2
удовлетворяют
уравнению
x
1
≡ x
2
( mod m ), где m = m
1
· m
2
· ... · m
n
.
В трактате другого китайского математика Джу Шао Квина
(Jiushao Qin) (1247 г. н.э.) дается формула для вычисления числа x,
удовлетворяющего теореме:
x =
n
i=0
r
i
· e
i
, где e
i
=
m
m
i
·
m
m
i
−1
mod m
i
, 1 ≤ i ≤ n. (2.18)
Заметим, что поскольку число m
i
взаимно просто с m/m
i
, то обратное
число в формуле для e
i
всегда существует для 1 ≤ i ≤ n. Кроме того, имеют
место равенства
e
i
· e
i
≡ e
i
( mod m ),
e
i
· e
j
≡ 0 ( mod m ) при i ̸= j ,
т.е. компоненты 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
.
(2.19)
Достоинство этого алгоритма заключается в том, что вычисление каждого
последующей пары (x
i+1
, y
i+1
) использует только одно предыдущее значение
(x
i
, y
i
), что позволяет последовательно уточнять значения корня x.
                                                                                  44

всех 1 ≤ i ≤ n. Более того, любые два таких числа x1 и x2 удовлетворяют
уравнению

       x1 ≡ x2 ( mod m ), где m = m1 · m2 · ... · mn .

      В трактате другого китайского математика Джу Шао Квина
(Jiushao Qin) (1247 г. н.э.) дается формула для вычисления числа x,
удовлетворяющего теореме:
                                         ((        )−1         )
         ∑
         n
                                  m           m
    x=         ri · ei , где ei =    ·                   mod mi , 1 ≤ i ≤ n.   (2.18)
         i=0
                                  mi          mi

      Заметим, что поскольку число mi взаимно просто с m/mi , то обратное
число в формуле для ei всегда существует для 1 ≤ i ≤ n. Кроме того, имеют
место равенства
        {
          ei · ei ≡ ei ( mod m ),
            ei · ej ≡ 0 ( mod m ) при i ̸= j,
т.е. компоненты ei взаимно ортогональны по модулю m.

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

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

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

Страницы