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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Простые алгоритмы факторизации 66
и, соответственно,
x
i+1
=
tx
i
mod p, если 0 < x
i
< p/3,
x
2
i
mod p, если p/3 < x
i
< 2p/3,
gx
i
mod p если 2p/3 < x
i
< p,
(2.28)
Эта последовательность вычисляется до тех пор, пока не появятся номера
i, j такие, что x
i
= x
j
. Тогда, t
a
i
g
b
i
= t
a
j
g
b
j
, откуда,
(a
j
− a
i
)k ≡ b
i
− b
j
(mod(p − 1)) (2.29)
Если Н.О.Д.(a
j
−a
i
, p−1) = 1, тогда множитель k в уравнении (2.29) может
быть найден с использованием обобщенного алгоритма Евклида, решив в
целых числах уравнение
x(a
j
− a
i
) + y(p − 1) = b
i
− b
j
(2.30)
относительно x, y и определяя k = x mod (p − 1).
Если же Н.О.Д.(a
j
− a
i
, p − 1) = d > 1, тогда, уравнение (2.30) по-
прежнему, разрешимо, но дает решение нашего уравнения с точностью до
слагаемого кратного (p −1)/d, т.е. решение имеет вид
x = x
0
+ m(p − 1)/d (2.31)
где m ∈ [0, d − 1]–целое число. Если множитель d - мал, то решение будет
найдено подстановкой чисел (2.31) в уравнение g
X
≡ t mod t.
Так же, как в ρ–методе факторизации, в этом алгоритме можно
использовать модификацию Флойда, вычисляя на i-м шаге одновременно
тройку (a
i
, b
i
, x
i
) и тройку (a
2i
, b
2i
, x
2i
), пока не дойдем до шага i, на котором
x
i
= x
2i
. В этом варианте опять не надо хранить в памяти на шаге i все
тройки (a
j
, b
j
, x
j
) для j ≤ i, а достаточно сохранять две тройки (a
i
, b
i
, x
i
) и
(a
2i
, b
2i
, x
2i
).
Пример. Рассмотрим поле F
p
при p = 43. Элемент g = 2 не является
генератором по критерию Поклингтона (см.стр.19), т.к.2
14
mod 43 = 1.
Возьмем в качестве генератора элемент g = 3 и решим уравнение
3
X
mod 43 = 15. (2.32)
Глава 2. Простые алгоритмы факторизации                                              66

и, соответственно,
                               
                                txi mod p,    если 0 < xi < p/3,
                               
                               
                      xi+1   =   x2i mod p,    если p/3 < xi < 2p/3,             (2.28)
                               
                                gxi mod p
                               
                                               если 2p/3 < xi < p,

Эта последовательность вычисляется до тех пор, пока не появятся номера
i, j такие, что xi = xj . Тогда, tai g bi = taj g bj , откуда,

                      (aj − ai )k ≡ bi − bj (mod(p − 1))                         (2.29)

Если Н.О.Д.(aj − ai , p − 1) = 1, тогда множитель k в уравнении (2.29) может
быть найден с использованием обобщенного алгоритма Евклида, решив в
целых числах уравнение

                       x(aj − ai ) + y(p − 1) = bi − bj                          (2.30)

относительно x, y и определяя k = x mod (p − 1).
          Если же Н.О.Д.(aj − ai , p − 1) = d > 1, тогда, уравнение (2.30) по-
прежнему, разрешимо, но дает решение нашего уравнения с точностью до
слагаемого кратного (p − 1)/d, т.е. решение имеет вид

                                    x = x0 + m(p − 1)/d                          (2.31)

где m ∈ [0, d − 1]–целое число. Если множитель d - мал, то решение будет
найдено подстановкой чисел (2.31) в уравнение g X ≡ t mod t.
          Так же, как в ρ–методе факторизации, в этом алгоритме можно
использовать модификацию Флойда, вычисляя на i-м шаге одновременно
тройку (ai , bi , xi ) и тройку (a2i , b2i , x2i ), пока не дойдем до шага i, на котором
xi = x2i . В этом варианте опять не надо хранить в памяти на шаге i все
тройки (aj , bj , xj ) для j ≤ i, а достаточно сохранять две тройки (ai , bi , xi ) и
(a2i , b2i , x2i ).

          Пример. Рассмотрим поле Fp при p = 43. Элемент g = 2 не является
генератором по критерию Поклингтона (см.стр.19), т.к.214 mod 43 = 1.
Возьмем в качестве генератора элемент g = 3 и решим уравнение

       3X mod 43 = 15.                                                           (2.32)

Страницы