Глава 11.

МЕТОДЫ ФАКТОРИЗАЦИИ ПОЛЛАРДА

Основное в этой главе…

(P-1) - метод факторизации Полларда…..………………………...142

Pо - метод факторизации Полларда……………….……...…….144

i

p −1 =∏pimi ,

142 Глава11. МЕТОДЫФАКТОРИЗАЦИИ ПОЛЛАРДА

При анализе криптосистемы RSA легко обнаружить, что сложность задачи факторизации модуля N = pq , на которой основана стойкость системы,

зависит от соотношений между сомножителями, например, от величины разности q − p .

На сложность факторизации влияют, кроме того, индивидуальные особенности каждого из сомножителей, выраженные как теоретико-числовые свойства некоторых функций от p и q [47].

11.1. (P-1) - метод факторизации Полларда

Рассмотрим метод разложения числа n на сомножители, известный как

(p −1)-метод	факторизции		Полларда.	Метод является		частным,		т.е. он
применим не для каждого n .
Фактически, (p −1)-метод Полларда является оптимизацией следующего
подхода.
Пусть p -	нетривиальный делитель числа n. Перебираем пары чисел a,t .
На каждом шаге вычисляем наибольший					общий делитель		двух чисел
d = (at −1,n).	Если	at	=1mod p ,	но	at ≠1 mod n ,	то	d	является
нетривиальным делителем n.
Пусть дано нечетное натуральное число					n = pq , где p - его наименьший

простой делитель и (p,q)=1. Рассмотрим задачу факторизации n при условии,

что число p −1 является гладким, т.е., i pi ≤ B , где B -

граница, определяемая вычислительными возможностями при реализации алгоритма.

Допустим, для некоторого a, (a,n)=1, нам удалось локализовать значение ordp a, которое, очевидно, делит p −1.

ord pa

(Р-1) - метод факторизации Полларда 143

Например, удалось найти число v , удовлетворяющее следующим условиям:

1)v делится на ordp a;

2)av =1mod p , но av ≠1 mod n .

В этом случае, поскольку av −1 не делится на n, мы можем определить

d = (av −1,n), где d < n , d = λp .

Все сводится к тому, как построить число v и воспользоваться его свойствами, при неизвестном p .

Сначала, в зависимости от вычислительных возможностей, выберем параметр k и построим число v = v(k) так, чтобы заведомо v(k) делилось на

p −1.

Например, v(k)= k!, либо v(k )=НОК(1,2,Kk), где k ≈ n , поскольку

p < n . Данный этап является неформальным и наиболее сложным.

Не исключено, что следует выбирать v(k )= m(k )h как степень произведения всех, либо части простых чисел, меньших B, поскольку p −1

может делиться на высокие степени малых простых чисел. По возможности, h следует выбирать, начиная с минимального значения.

Если p −1 делит v(k), то порядки всех чисел a, взаимно простых с p, также делят v(k). Следовательно av =1mod p . Поскольку необходимо,

чтобы av	≠1 mod n , то очевидно, что v не должно делиться на ϕ(n).
При	этом все же	нельзя	утверждать, что av ≠1 mod n , поскольку
возможен	случай, когда	ordna	делит v(k ). Поэтому, при (av −1,n)= n

(av −1,n)= n .

144 Глава11. МЕТОДЫФАКТОРИЗАЦИИ ПОЛЛАРДА

необходимо псевдослучайно выбрать новое значение a и повторить вычисление

(av −1,n).

Пример.

Найти нетривиальный делитель d числа n = 2431 = p1 p2 p3 =11 13 17 .

Выберем относительно небольшое значение k, скажем, k = 4 n = 7 .

Заметим, что если выбрать v(k )= (2 3 5 7)4 , то мы не сможем решить задачу. Действительно, все ϕ(pi ), i =1,2,3 делят v(k ), следовательно, для всех a, взаимно простых с n ,

Пусть v(k )= (2 3 5 7)2 = 2102 . В данном случае ϕ(17) не делит v(k ).

Конечно, заранее это не может быть известно.

Выберем a: (a,n)=1, например, a =3.

Вычислим av −1 = 3210 210 -1 mod n .

Получим:

av −1 ≡ 3180 -1 ≡1287mod 2431, d =НОД(1287, 2431)=143.

11.2. Pо - метод факторизации Полларда

Следующий метод, который мы рассмотрим, носит название ро-метода Полларда. Название связано с тем, что метод осуществляет случайный поиск, используя свойства цикличности некоторых последовательностей.

Эти последовательности не являются чисто периодическими, а имеют так называемые подходы к циклам, что графически выглядит как греческая буква

ρ (ро).

(Pо) - метод факторизации Полларда 145

Данный метод эффективнее, чем метод полного перебора делителей n . Кроме того, идея метода применима и в других ситуациях, например, для логарифмирования в группах точек эллиптических кривых.

В ро-методе	прежде всего выбирается некоторое отображение
f : Z nZ → Z nZ	кольца вычетов по модулю n в себя. Необходимо, чтобы

значения этого отображения можно было бы вычислить достаточно быстро.

Например,	это может быть		полином с		целыми		коэффициентами, скажем,
f (x)= x2 + x +1modn .
Затем	псевдослучайно		выбирается		число	x0	(начальное значение) и
рассматриваются		элементы	последовательности				итераций:	xj+1 = f (xj ),
j = 0,1,2,K, то есть x1 = f (x0 ),				x2 = f (x1 ), x3 = f (f (f (x0 ))) и т.д.
Очевидно, данная последовательность циклическая не только как
последовательность вычетов			по	модулю n , но и как последовательность
вычетов по некоторому простому делителю p <						n числа n.
Будем рассматривать пары элементов последовательности.
Среди	этих	пар найдутся		такие, скажем		xj , xk , что		xj ≠ xk (n), но
xj = xk (p).	Если	такая пара,		назовем	ее критической, попадется среди

рассматриваемого множества пар, то можно найти собственный делитель r числа n вида r = (xj − xk ,n)= λp .

Пример. Найти нетривиальный делитель числа n = 2431.

Выберем	f (x)= x2 + x +1, x0 = 2431 =50. Вычисляем рекурренту и
проверяем	пары:	x =50 (2431),	x =502	+50 +1 =120(2431),
		0	1

x2 = 2366 (2431), x3 =1730 (2431), x4 = 2070(2431) и так далее.