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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

36
5. Найдем y = z
s
( mod p) = 3
5
( mod 41) = 38.
6. Вычислим степень, в которую надо возводить y :
d = 2
r−m
= 2
3−2
= 2, y
d
= 3
2
= 9.
7. Вычислим λ
1
= λ
0
·y
d
( mod p) = 32 ·9( mod 41) = 1, w
1
= w
0
·y
d−1
( mod
p) = 8 · 3( mod 41) = 24. Поскольку очередное λ
i
оказалось равным 1, то
процедура закончена. Корень x = w
1
= 24. Выполним проверку:
x
2
mod p = 24
2
mod 41 = 2 = a.
1.15. Китайская теорема об остатках
Китайская теорема об остатках позволяет вычислить целое число, если
известны его остатки по нескольким простым модулям. Впервые эта теорема
была упомянута в трактате китайского математика Сунь Цзы, примерно в
третьим веком до н.э.
Теорема 1.8. Если натуральные числа m
1
, m
2
, ..., m
n
попарно взаимно
просты, то для любых целых r
1
, r
2
, ..., r
n
таких, что 0 ≤ r
1
< m
i
при
всех i, найдётся число x, которое при делении на m
i
даёт остаток r
i
при
всех 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
X
i=0
r
i
· e
i
, где e
i
=
m
m
i
·
m
m
i
−1
mod m
i
!
, 1 ≤ i ≤ n. (1.15)
Заметим, что поскольку число 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 6= j,
                                                                                 36

5. Найдем y = z s ( mod p) = 35 ( mod 41) = 38.

6. Вычислим степень, в которую надо возводить y :
       d = 2r−m = 23−2 = 2,        y d = 32 = 9.

7. Вычислим λ1 = λ0 · y d ( mod p) = 32 · 9( mod 41) = 1, w1 = w0 · y d−1 ( mod
p) = 8 · 3( mod 41) = 24. Поскольку очередное λi оказалось равным 1, то
процедура закончена. Корень x = w1 = 24. Выполним проверку:

      x2 mod p = 242 mod 41 = 2 = a.


1.15. Китайская теорема об остатках
      Китайская теорема об остатках позволяет вычислить целое число, если
известны его остатки по нескольким простым модулям. Впервые эта теорема
была упомянута в трактате китайского математика Сунь Цзы, примерно в
третьим веком до н.э.

Теорема 1.8. Если натуральные числа m1 , m2 , ..., mn попарно взаимно
просты, то для любых целых r1 , r2 , ..., rn таких, что 0 ≤ r1 < mi при
всех i, найдётся число x, которое при делении на mi даёт остаток ri при
всех 1 ≤ i ≤ n. Более того, любые два таких числа x1 и x2 удовлетворяют
уравнению

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

      В трактате другого китайского математика Джу Шао Квина
(Jiushao Qin) (1247 г. н.э.) дается формула для вычисления числа x,
удовлетворяющего теореме:
         n                                       −1         !
         X                        m          m
    x=         ri · ei , где ei =    ·                  mod mi , 1 ≤ i ≤ n.   (1.15)
         i=0
                                  mi         mi
      Заметим, что поскольку число mi взаимно просто с m/mi , то обратное
число в формуле для ei всегда существует для 1 ≤ i ≤ n. Кроме того, имеют
место равенства
        (
          ei · ei ≡ ei ( mod m ),
            ei · ej ≡ 0 ( mod m ) при i 6= j,

Страницы