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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Криптостойкость RSA. Алгоритмы факторизации 57
Вместо функции 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].
int ρ-Pollard (int n)
{ int x = random (1, n-2);
int y = 1; int i = 0; int stage = 2;
while(Н.О.Д.(n, abs(x − y)) = 1)
{
if (i = = stage ){
y = x;
stage = stage*2; }
x=x ∗ x + 1(modn);
i=i + 1;
}
return Н.О.Д.(n, abs(x − y)); }
В этом варианте вычисление требует хранить в памяти всего три
переменные n, x и y , что выгодно отличает этот метод от других методов
факторизации.
Еще одна вариация ρ-метода Полларда была разработана Флойдом
(Floyd). Согласно Флойду, значение y обновляется на каждом шаге по
формуле y = F
2
(y) = F (F (y)), поэтому на шаге i будут получены значения
Глава 2. Криптостойкость RSA. Алгоритмы факторизации                    57

        Вместо функции 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].
         int ρ-Pollard (int n)
         { int x = random (1, n-2);
         int y = 1; int i = 0; int stage = 2;
         while(Н.О.Д.(n, abs(x − y)) = 1)
         {
             if (i = = stage ){
                  y = x;
                  stage = stage*2; }
             x=x ∗ x + 1(modn);
             i=i + 1;
         }
         return Н.О.Д.(n, abs(x − y)); }
        В этом варианте вычисление требует хранить в памяти всего три
переменные n, x и y , что выгодно отличает этот метод от других методов
факторизации.
        Еще одна вариация ρ-метода Полларда была разработана Флойдом
(Floyd). Согласно Флойду, значение y обновляется на каждом шаге по
формуле y = F 2 (y) = F (F (y)), поэтому на шаге i будут получены значения

Страницы