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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

42
т.е. порядок элемента y равен в точности 2
r
. Вычислим далее элементы
λ
0
= a
s
( mod p), w
0
= a
(s+1)/2
( mod p). (2.14)
Заметим, что
w
2
0
≡ a · λ
0
( mod p) и x
2
≡ a( mod p) → x
2s
≡ a
s
= λ
0
( mod p). (2.15)
Поскольку порядок элемента x
s
является делителем 2
r
, то порядок
λ
0
является делителем 2
r−1
. Идея метода Шенкса–Тоннелли состоит
в построении последовательности пар чисел (λ
i
, w
i
), удовлетворяющих
условию
w
2
i
≡ a · λ
i
( mod p), i = 0, 1, 2, ... , (2.16)
причем порядок λ
i+1
является собственным делителем порядка λ
i
, до
тех пор, пока порядок очередного λ
i
не окажется равным 0. Тогда для
найденного i выполнятся условия λ
i
= 1 и
w
2
i
≡ a ( mod p),
откуда x = w
i
является искомым корнем.
Поскольку исходные значения (λ
0
, w
0
), удовлетворяющие (2.16),
согласно (2.15), уже определены, то осталось просто описать формулы для
вычисления значений (λ
i+1
, w
i+1
):
λ
i+1
= λ
i
· y
2
r−m
, w
i+1
= w
i
· y
2
r−m−1
, (2.17)
где 2
m
–порядок элемента λ
i
.
Пример. Рассмотрим пример вычисления квадратного корня из a = 2
в простом поле GF
p
при p = 41:
1. Имеем, p − 1 = 40 = 2
3
· 5, откуда, s = 5, r = 3.
2. Вычислим исходные значения (λ
0
, w
0
) по формулам (2.14):
λ
0
= a
s
( mod p) = 2
5
( mod 41) = 32,
                                                                        42

т.е. порядок элемента y равен в точности 2r . Вычислим далее элементы

      λ0 = as ( mod p), w0 = a(s+1)/2 ( mod p).                     (2.14)

      Заметим, что

 w02 ≡ a · λ0 ( mod p) и x2 ≡ a( mod p) → x2s ≡ as = λ0 ( mod p).   (2.15)

      Поскольку порядок элемента xs является делителем 2r , то порядок
λ0 является делителем 2r−1 . Идея метода Шенкса–Тоннелли состоит
в построении последовательности пар чисел (λi , wi ), удовлетворяющих
условию

    wi2 ≡ a · λi ( mod p), i = 0, 1, 2, ... ,                       (2.16)

причем порядок λi+1 является собственным делителем порядка λi , до
тех пор, пока порядок очередного λi не окажется равным 0. Тогда для
найденного i выполнятся условия λi = 1 и

          wi2 ≡ a ( mod p),

откуда x = wi является искомым корнем.
      Поскольку исходные значения (λ0 , w0 ), удовлетворяющие (2.16),
согласно (2.15), уже определены, то осталось просто описать формулы для
вычисления значений (λi+1 , wi+1 ):
                 r−m                         r−m−1
   λi+1 = λi · y 2     ,   wi+1 = wi · y 2           ,              (2.17)

где 2m –порядок элемента λi .

      Пример. Рассмотрим пример вычисления квадратного корня из a = 2
в простом поле GFp при p = 41:

1. Имеем, p − 1 = 40 = 23 · 5, откуда, s = 5, r = 3.

2. Вычислим исходные значения (λ0 , w0 ) по формулам (2.14):

     λ0 = as ( mod p) = 25 ( mod 41) = 32,

Страницы