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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

43
w
0
= a
(s+1)/2
( mod p) = 2
3
( mod 41) = 8.
3. Найдем порядок элемента λ
0
:
λ
2
0
mod p = 32
2
mod 41 = 40 ≡ −1 ( mod 41), λ
4
0
≡ 1 mod p.
Отсюда, ord(λ
0
) = 2
m
= 4, m = 2.
4. Будем искать квадратичный невычет. Вычислим символ Лежандра для
z = 3:
(
z
p
)
=
(
3
41
)
=
(
41 mod 3
3
)
(−1)
(41−1)(3−1)/2
=
(
2
3
)
= −1,
значит, z = 3 является квадратичным невычетом и может быть использован
для вычисления пар (λ
i+1
, w
i+1
).
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.
2.17. Китайская теорема об остатках
Китайская теорема об остатках позволяет вычислить целое число, если
известны его остатки по нескольким простым модулям. Впервые эта теорема
была упомянута в трактате китайского математика Сунь Цзы, примерно в
третьим веком до н.э.
Теорема 2.8. Если натуральные числа m
1
, m
2
, ..., m
n
попарно взаимно
просты, то для любых целых r
1
, r
2
, ..., r
n
таких, что 0 ≤ r
1
< m
i
при
всех i, найдётся число x, которое при делении на m
i
даёт остаток r
i
при
                                                                            43

     w0 = a(s+1)/2 ( mod p) = 23 ( mod 41) = 8.

3. Найдем порядок элемента λ0 :

      λ20 mod p = 322 mod 41 = 40 ≡ −1 ( mod 41), λ40 ≡ 1 mod p.

      Отсюда, ord(λ0 ) = 2m = 4, m = 2.

4. Будем искать квадратичный невычет. Вычислим символ Лежандра для
z = 3:
   ( ) ( ) (          )                     ( )
    z    3    41 mod 3                       2
       =    =           (−1)(41−1)(3−1)/2 =     = −1,
    p    41       3                          3
значит, z = 3 является квадратичным невычетом и может быть использован
для вычисления пар (λi+1 , wi+1 ).

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.


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

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

Страницы