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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Простые алгоритмы факторизации 62
1. Выбираем небольшое число x
0
и строим последовательность чисел
{x
n
}, n = 0, , 1, 2, ..., определяя каждое следующее x
n+1
по формуле
x
n+1
= (x
2
n
− 1) (mod n).
2. Одновременно на каждом шаге i вычисляем Н.О.Д d числа n и
всевозможных разностей |x
i
− x
j
|, где j < i.
3. Когда будет найдем d =Н.О.Д.(n, |x
i
−x
j
|), отличный от 1, вычисление
заканчивается. Найденное d является делителем n. Если n/d не
является простым числом, то процедуру можно продолжить, взяв
вместо n число n/d.
Вместо функции F (x) = (x
2
− 1) mod n в вычислении x
n+1
можно
взять другой многочлен, например, x
2
+ 1 или произвольный многочлен 2-й
степени F (x) = ax
2
+ bx + c.
Недостатком данного варианта метода является необходимость
хранить большое число предыдущих значений x
j
. Заметим, что если
(x
j
− x
i
) ≡ 0 ( mod p), то (f(x
j
) − f(x
i
)) ≡ 0 ( mod p),
поэтому, если пара (x
i
, x
j
) дает нам решение, то решение даст любая пара
(x
i+k
, x
j+k
).
Поэтому, нет необходимости проверять все пары (x
i
, x
j
), а можно
ограничиться парами виды (x
i
, x
j
), где j = 2
k
, и k пробегает набор
последовательных значений 1, 2, 3, ..., а i принимает значения из интервала
[2
k
+ 1; 2
k+1
]. Например, при k = 3 j = 2
3
= 8, а i ∈ [9; 16].
Глава 2. Простые алгоритмы факторизации                                 62

   1. Выбираем небольшое число x0 и строим последовательность чисел
      {xn }, n = 0, , 1, 2, ..., определяя каждое следующее xn+1 по формуле
      xn+1 = (x2n − 1) (mod n).

   2. Одновременно на каждом шаге i вычисляем Н.О.Д d числа n и
      всевозможных разностей |xi − xj |, где j < i.

   3. Когда будет найдем d =Н.О.Д.(n, |xi −xj |), отличный от 1, вычисление
      заканчивается. Найденное d является делителем n. Если n/d не
      является простым числом, то процедуру можно продолжить, взяв
      вместо n число n/d.

        Вместо функции F (x) = (x2 − 1) mod n в вычислении xn+1 можно
взять другой многочлен, например, x2 + 1 или произвольный многочлен 2-й
степени F (x) = ax2 + bx + c.
        Недостатком данного варианта метода является необходимость
хранить большое число предыдущих значений xj . Заметим, что если

(xj − xi ) ≡ 0 ( mod p), то (f (xj ) − f (xi )) ≡ 0 ( mod p),

поэтому, если пара (xi , xj ) дает нам решение, то решение даст любая пара
(xi+k , xj+k ).
        Поэтому, нет необходимости проверять все пары (xi , xj ), а можно
ограничиться парами виды (xi , xj ), где j = 2k , и k пробегает набор
последовательных значений 1, 2, 3, ..., а i принимает значения из интервала
[2k + 1; 2k+1 ]. Например, при k = 3 j = 23 = 8, а i ∈ [9; 16].

Страницы