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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

35
причем порядок λ
i+1
является собственным делителем порядка λ
i
, до
тех пор, пока порядок очередного λ
i
не окажется равным 0. Тогда для
найденного i выполнятся условия λ
i
= 1 и
w
2
i
≡ a ( mod p),
откуда x = w
i
является искомым корнем.
Поскольку исходные значения (λ
0
, w
0
), удовлетворяющие (1.13),
согласно (1.12), уже определены, то осталось просто описать формулы для
вычисления значений (λ
i+1
, w
i+1
):
λ
i+1
= λ
i
· y
2
r−m
, w
i+1
= w
i
· y
2
r−m−1
, (1.14)
где 2
m
–порядок элемента λ
i
.
Пример. Рассмотрим пример вычисления квадратного корня из a = 2
в простом поле GF
p
при p = 41:
1. Имеем, p − 1 = 40 = 2
3
· 5, откуда, s = 5, r = 3.
2. Вычислим исходные значения (λ
0
, w
0
) по формулам (1.11):
λ
0
= a
s
( mod p) = 2
5
( mod 41) = 32,
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
).
                                                                      35

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

         wi2 ≡ a ( mod p),

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

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

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

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

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

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

     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     (41−1)(3−1)/2    2
       =    =          (−1)              =     = −1,
    p    41       3                         3
значит, z = 3 является квадратичным невычетом и может быть использован
для вычисления пар (λi+1 , wi+1 ).

Страницы