Глава 3. Факторизация целых чисел с субэкспоненциальной сложностью

§ 3.1. Введение

В данной главе мы рассматриваем алгоритмы факторизации натуральных чисел n, делающие Ln [ ; c] арифметических операций при

= 12 или = 13 и при некоторой положительной, зависящей от алгоритма, постоянной c. Алгоритмов факторизации, имеющих оценки сложности лучше указанных, в настоящее время не существует.

Мы предполагаем далее, что число n — составное (это быстро проверяется с помощью вероятностных алгоритмов из главы 1) и что n не делится на небольшие простые числа (все небольшие простые делители мы находим перебором, а также с помощью алгоритмов из главы 2).

Описываемые далее алгоритмы находят натуральные числа x, y такие, что x2 ≡ y2 (mod n), и затем проверяют условие

1 < НОД(x ± y, n) < n.

Если делитель n найден, то алгоритм останавливается, иначе строит следующую пару x, y.

Утверждение 3.1. Пусть n — нечетное составное число, не являющееся степенью простого числа. Тогда для случайной пары x, y, 1 x, y n − 1, удовлетворяющей соотношениям

НОД(x, n) = НОД(y, n) = 1, x2 = y2 (mod n),

вероятность того, что

1 < НОД(x ± y, n) < n,

будет не меньше 1/2.

Доказательство. Пусть n = p11 . . . pkk , k 2, есть разложение n на простые сомножители. Паре x, y, удовлетворяющей условиям утверждения, соответствует число z, 1 z n − 1, z2 ≡ 1 (mod n) (очевидно,

78 Гл. 3. Факторизация целых чисел с субэкспоненциальной сложностью

z = xy−1 (mod n)). Нам достаточно доказать, что количество таких z, для которых дополнительно выполнено неравенство

1 < НОД(z ± 1, n) < n,

будет не меньше половины. Очевидно, что условие z2 ≡ 1 (mod n) равносильно совокупности условий

z≡ ±1 (mod p11),

. . . . . . . . . . . . . . . . . .

z≡ ±1 (mod pkk),

где знаки ± произвольны. Отсюда количество возможных значений для z равно 2k, и только для двух значений z ≡ ±1 (mod n) наибольший общий делитель НОД(z ± 1, n) будет равен 1 или n. Поскольку k 2, то наше утверждение теперь очевидно.

Построение пар x, y таких, что x2 = y2 (mod n), будет неэффективным для факторизации n, равного степени простого числа p, т. е. n = p . Такие числа n довольно редки. Для их обнаружения можно предложить следующий способ. Если a N, p a, то ap ≡ a (mod p). Отсюда an ≡ a (mod p), и поэтому НОД(an − a, n) ... p, т. е. НОД(an − a, n) > 1. Поэтому, если для некоторого случайно выбранного a выполнено равенство НОД(an − a, n) = 1, то n = p . Если же для нескольких значений a окажется НОД(an − a, n) > 1, то мы либо разложим n на множители (если НОД(an − a, n) < n), либо будем считать n степенью простого числа и попробуем факторизовать его, извлекая корни степени 2, 3, 5, 7, . . . из n.

В описываемых далее алгоритмах мы будем считать дополнительно, что n не является степенью простого числа.

Везде в этой главе, за исключением двух последних параграфов, мы обозначаем L = L(n) = exp((log n log log n)1/2). Мы также будем предполагать, что n не делится на простые числа p такие, что p L(n); это

легко проверяется с помощью перебора за	( ( ))	= Ln	1	, 1 арифме-
тических операций.	O L n		2

§ 3.2. Метод Диксона. Дополнительные стратегии

Пусть n N — число, которое мы хотим разложить на множители, L = L(n) = exp((log n log log n)1/2). Пусть a — некоторая постоянная, 0 < a < 1, значение которой будет определено ниже. Факторной базой

§ 3.2. Метод Диксона. Дополнительные стратегии

79

мы будем называть множество простых чисел p, лежащих в промежутке 2 p La.

Пусть k — количество простых чисел в факторной базе, 2 = p1 < p2 < . . .

. . . < pk La. Символом Q(m) мы будем обозначать наименьший неотрицательный вычет в классе m2 (mod n).

Опишем алгоритм Диксона, следуя работе [221].

Алгоритм Диксона.

1 шаг. Случайным перебором ищем числа m1, . . . , mk+1 такие, что 1 < mi < n, Q(mi) = p1i,1 . . . pki,k

для i = 1, . . . , k + 1. Это означает, что m2i ≡ Q(mi) (mod n) являются гладкими числами, то есть раскладываются на множители в нашей факторной базе. Обозначим v¯i = ( i,1, . . . , i,k) Zk — векторы показателей в разложении Q(mi) на множители.

2 шаг. Решая систему линейных уравнений

x1v¯1 + . . . + xk+1v¯k+1 ≡ 0¯ (mod 2)

в векторном пространстве (Z/2Z)k,				находим значения x1, . . . , xk+1
{0, 1}, не все равные нулю			(такое решение существует, поскольку
число уравнений k меньше числа неизвестных).
3 шаг. Для найденных x1, . . . , xk справедливо соотношение
(mx1 . . . m k+1)2 p			k+1	. . .	k+1	(mod n).
					pi
	x		xi i,1		xi i,k
		≡	i=1		=1
1	k+1		1		k
Обозначая			Y = pj			,
X = m11 . . . mk+1 ,
					k+1
					k	xi i,j 2
	x	xk+1			j
					i=1
					=1
(числа k+1 xi i,j	2 — целые по определению xi), мы получим соот-

ношение i=1

X2 ≡ Y2 (mod n).

Далее проверяем условие

1 < НОД(X ± Y, n) < n.

В случае успеха мы разложили n на множители (вероятность успеха была оценена в § 3.1). В случае неудачи мы возвращаемся на 1 шаг и ищем другие значения mi.

Конец алгоритма.

80 Гл. 3. Факторизация целых чисел с субэкспоненциальной сложностью

Замечание 3.2. Факторизация чисел Q(mi) на 1 шаге алгоритма Диксона проводится пробными делениями на элементы факторной базы.

Замечание 3.3. Решение системы линейных уравнений на 2 шаге алгоритма можно проводить методом Гаусса.

Проанализируем сложность алгоритма Диксона, следуя работе [221]. При этом примем следующее соглашение. Вместо Lconst+o(1)

будем писать просто Lconst; величина o(1) все равно будет при-

1

сутствовать в итоговой оценке сложности Ln 2 ; c . Очевидно, что

const · Lconst = Lconst по нашему определению; также (Lconst) = Lconst, где (x) — число простых чисел, не превосходящих x.

Для одного случайно выбранного значения m на 1 этапе алгоритма поиск разложения Q(m) в нашей факторной базе составит La арифметических операций. Действительно, простых чисел p La в факторной базе будет k = (La) = La по нашему соглашению. Простое число p может входить в разложение Q(m) с кратностью p logp Q(m) log2 n. Следовательно, общее количество операций деления для разложения Q(m) на множители не будет превосходить величины

a	a		elog log n	a	o(1)	a
L	· log2 n = L	·		= L	· L	= L
			log 2

по нашему соглашению.

Пусть мы делали случайный выбор m на 1 этапе Lb раз для некоторой постоянной b. Тогда будет потрачено La+b арифметических операций на разложение Q(m) на множители. Если мы нашли k + 1 значение mi, то на 2-м этапе, решая систему линейных уравнений от k + 1 = La + 1 = La неизвестных методом Гаусса, мы потратим еще L3a арифметических операций. В работе [221] с помощью теорем о рас-

пределении простых чисел показано, что при b = a + 21a за Lb выборов числа m мы с высокой вероятностью найдем (La) + 1 = La = k + 1 значений mi таких, что Q(mi) раскладываются на множители из нашей факторной базы. Тогда суммарная оценка сложности алгоритма Диксона составит

		1
		Lmax(a+b,3a) = Lmax 2a+		,3a
			2a
	арифметических операций. Минимум величины max					2a +	1	, 3a
							2a
	на интервале (0; +	∞
					получаем оценку
		) достигается и равен 2. В итоге

§ 3.2. Метод Диксона. Дополнительные стратегии

81

сложности алгоритма при a = 1 :
2
L2 = Ln 21 ; 2
арифметических операций.
Вывод. Если факторная база состоит	из всех простых чисел
p L(n)1/2 и мы случайно выбираем L(n)3/2	значений m, то с высокой

вероятностью будет построена пара x, y N такая, что x2 = y2 (mod n).

1

При этом будет выполнено Ln 2 ; 2 арифметических операций (ес-

ли на 2 этапе алгоритма Диксона использовать обычное гауссово исключение для решения линейных систем).

Теперь обсудим дополнительные стратегии ускоряющие работу алгоритма Диксона (см. [221]).

Стратегия LP (использование больших простых чисел)

Эта стратегия была впервые предложена в работе [79]. Обычно она всегда используется на практике в субэкспоненциальных алгоритмах факторизации целых чисел и алгоритмах дискретного логарифмирования в конечных простых полях.

Суть стратегии LP заключается в следующем. Пусть мы раскладываем на множители Q(m) = m2 (mod n); поделили на все простые p La, и у Q(m) еще осталась неразложенная часть s, то есть

Q(m) = s · p p (m) .

p La

Очевидно, что s > La. Если дополнительно выполняется неравенство s L2a, то s — простое число (иначе у s был бы простой делитель, не превосходящий √s La). Тогда мы включаем дополнительное большое простое число s в факторную базу и храним те значения m, для которых Q(m) делится на данное s. Это увеличивает длину векторов-показателей на 1 этапе алгоритма. Для того, чтобы вернуться к исходной длине векторов k, после выполнения 1 этапа следует провести исключение дополнительных больших простых чисел. А именно, если в нашем списке есть дополнительное большое простое число s, и только одно Q(m) делится на него, то мы вычеркиваем s и Q(m) из списка. Если же, например, есть два значения Q(m1) и Q(m2), делящиеся на s, то значение Q(m1) · Q(m2) ≡ (m1m2)2 (mod n) будет делиться на s2. Следовательно, показатель числа s войдет в вектор

6 О. Н. Василенко

Lmax(a2 +b,3a)

ставляет Ln

Q(m) =

82 Гл. 3. Факторизация целых чисел с субэкспоненциальной сложностью

показателей в четной степени и будет отсутствовать в системе линейных уравнений над Z/2Z.

Можно использовать стратегию LP с двумя, тремя и т. д. дополнительными большими простыми числами, то есть искать такие m N,

для которых m2 ≡ Q(m) (mod n) и

p p (m) · s1s2 . . . st,

p La

где s1, . . . , st — дополнительные большие простые числа, не содержащиеся в факторной базе. В этом случае для исключения дополнительных простых чисел используется теория графов: строится граф, в котором затем ищутся циклы, дающие четную степень произведений

s1, . . . , st.

Замечание 3.4. Теоретическая оценка сложности алгоритма Дик-

сона с применением стратегии LP не улучшается и по-прежнему со-

1

2 ; 2 арифметических операций.

Стратегия PS (применение алгоритма Полларда—Штрассена)

В § 2.6 мы описали алгоритм Полларда—Штрассена, который для

z N	и	y	=	2	находит наименьший простой делитель числа НОД( ,		y	!)
			2	z	2	t
за O(z log				z log		t) арифметических операций.

Применительно к алгоритму Диксона мы хотим в числе Q(m) выделить часть разложения на простые множители, состоящую из простых чисел p, p La. Тогда полагаем z = [La/2] + 1, y = z2 La, y La и применяем алгоритм Полларда—Штрассена не более, чем log2 n раз при t = Q(m). В итоге мы выделим у числа Q(m) разложение на p La за O(log n · La/2 log4 n) = La/2 арифметических операций (по нашему соглашению). Следовательно, оценка сложности алгоритма Диксона составит

арифметических операций.

Теорема 3.5. Сложность алгоритма Диксона со стратеги-

ей PS минимальна при a =

1

=

+

1

и составляет Ln

1

√

;

3

арифметических операций√.

3

и b

a

2a

2

Стратегия EAS (стратегия раннего обрыва)

Пусть a, c, — некоторые фиксированные постоянные, 0 < a, c, < < 1. В алгоритме Диксона мы факторизовали Q(m) пробными делени-

§ 3.3. Алгоритм Бриллхарта—Моррисона

83

ями на p La. В стратегии EAS мы сначала делаем пробные деления Q(m) на p La , и если после этого неразложенная часть Q(m) остается больше, чем n1−c, то мы отбрасываем данное m и переходим к следующему. В работе [221] проведен детальный анализ стратегии EAS.

Теорема					3.6. Алгоритм Диксона								со					стратегией EAS	при
																		b
a =		2		, c =	1	,	=	1		1	;				7
									делает Ln									арифметических	опе-
		7			7			2		2					2

раций. При этом мы перебираем m в количестве L значений при b = a + 2ca + 12−ac .

Замечание 3.7. Можно проводить стратегию EAS с несколькими обрывами, то есть при некоторой возрастающей последовательности i и убывающей последовательности ci.

Методы исключения

Имеются более тонкие, чем алгоритм Гаусса, методы решения линейных систем уравнений над конечными полями. О них будет рассказано в последней главе книги. Например, в работе [98] предложен алгоритм решения систем линейных уравнений от k неизвестных в поле Z/2Z за O(k2,495548) арифметических операций.

Теорема 3.8. Алгоритм Диксона со стратегиями PS, EAS с несколькими обрывами и алгоритмом решения линейной системы уравнений от k неизвестных за O(k ) арифметических

операций при < 5/2 имеет оценку сложности Ln 12 ; 52 ариф-

метических операций.

Замечание 3.9. Алгоритм Диксона представляет собой очень удобную модель для получения теоретических оценок сложности без использования каких-либо эвристических и недоказанных гипотез. Однако, на практике он не применяется; вместо случайного выбора m используются другие подходы, о которых мы расскажем в следующих параграфах.

§ 3.3. Алгоритм Бриллхарта—Моррисона

В алгоритме Бриллхарта—Моррисона случайный выбор m из алгоритма Диксона заменяется на детерминированное определение очередного значения m, для которого мы ищем разложение m2 (mod n) на простые множители из факторной базы. Этот выбор m делается

6*

84 Гл. 3. Факторизация целых чисел с субэкспоненциальной сложностью

√

с помощью непрерывных дробей для числа n. Алгоритм впервые был описан в работе [79]; с его помощью было разложено на множители число Ферма F7. Данный метод факторизации был наиболее популярным до появления в 1981 г. алгоритма квадратичного решета Померанса, о котором будет рассказано в следующем параграфе. Об алгоритме

Бриллхарта—Моррисона см. также [25; 285].
Алгоритм основан на следующей теореме.
√					pi
Теорема 3.10. Пусть n N, n > 16, n N. Обозначим через						,
					qi
i = 0, 1, 2, . . . подходящие дроби для разложения √				в непрерыв-
			n

ную дробь. Тогда абсолютно наименьший вычет pi2

(mod n) равен

pi2 − nqi2 и выполняется неравенство

2

2

√

|pi − nqi

| < 2 n.

Доказательство. Обозначим

x = √

> 1. Тогда

по

свойствам

n

непрерывных дробей получим

2

2

2

x −

pi

x +

pi

|pi

− nqi |

= qi ·

·

<

qi

qi

2

pi+1

pi

pi

qi

pi

< qi

x +

=

x

+

.

qi+1

− qi

·

qi

qi

·

qi+1

Далее,

+ x +

p

p +1

p

= 2x

1

x +

i

< x

i

−

i

+

,

qi

qi+1

qi

qiqi+1

pi+1

pi

поскольку

и

расположены

по разные

стороны от x. Следова-

q

q

тельно,

i+1

i

pi2

−

x2qi2

| −

2x < 2x

−

1 +

qi

+

1

<

qi+1

|

2xqi2+1

<

2x −1 +

qi

+

1

= 2x −1

+

qi + 1

0,

qi+1

qi+1

qi+1

если i 1 (так как тогда qi + 1 qi+1). Отсюда при i 1 получим

|p2i − nq2i | < 2x = 2√n < n2 ,

так как n > 16. Это означает, что при i 1 выполнено утверждение

теоремы 3.10.

√

√

При i = 0, p0 = [

n], q0 = 1 и при

n} получим

= {

√

2

√

2

√

2

√

√

n]

− n| =

− n|

= | − 2

n +

| =

|[

|( n − )

(2

n − ) < 2 n.

Теорема доказана.

§ 3.3. Алгоритм Бриллхарта—Моррисона

85

Разложение √

в непрерывную дробь легко может быть найдено

n

по следующей теореме.

Теорема

3.11. Пусть

— квадратичная

иррациональность,

√

u

√

=

D

−

2

,

где D

N,

D

N, v

N, u

Z,

v

|

D

−

u. Тогда для

v

любого k 0 справедливо разложение в непрерывную дробь

= [a0, a1, . . . , ak, k+1],

где a0 Z, a1, . . . , ak N, k+1 — (k + 1)-й остаток. При этом справедливы соотношения:

	a0 = [ ],	v0 = v,		u0 = u + a0v
и при k 0							√
		D − uk2							+ uk
								D
ak+1 = [ k+1	], где vk+1 =		Z,	vk+1 = 0,		k+1 =				> 1,
		vk					vk+1

а числа uk получаются с помощью рекуррентной формулы uk+1 = ak+1vk+1 − uk.

Доказательство. Проведем индукцию по k. При k = 0 имеем

1

1

v

1 =

=

√

− u

=

√

− u − va0

=

− a0

D

a

D

v

− 0

=

√

v

0

=

√D + u

0

=

√D + u

0

.

2

v

D − u0

Число v1 — целое, поскольку

(D − u0)/v0

1

D − u02 = D − (u + a0v)2

= D − u2

2a u

a2v

Z

v0

v

v

−

0

− 0

по условию. Очевидно также, что v1 = 0 так как D = u2.

Пусть формулы теоремы 3.11 справедливы для номера k + 1. Докажем, что они выполнены и для k + 2. По определению (k + 2)-го остатка выполнены равенства

k+2 =

1

=

√

1

=

√

vk+1

=

k+1 − ak+1

+ uk

+ uk

ak+1vk+1

D

− ak+1

D

−

vk+1

√

√

v

+ u

+ u

=

√

k+1

=

D

k+1

=

D

k+1

.

2

v

D − uk+1

(D − uk+1)/vk+1

k+2

86 Гл. 3. Факторизация целых чисел с субэкспоненциальной сложностью

По определению неполного частного ak+2 = [ k+2]. Осталось лишь до-

казать, что v D − u2+ является целым числом. Число

k 1

k+2 =

vk+1

	vk+2 =	D − uk2+1	=	D − (ak+1vk+1 − uk)2
		vk+1		vk+1	D − uk2
	будет целым тогда и только тогда, когда целым будет число					= vk;
					v
	но vk — целое по предположению индукции.				k+1
	Следствие 3.12. По теореме 3.11 мы найдем разложение √
							n

в непрерывную дробь, используя только операции с целыми чис-
	√		+ u	.
лами и нахождения целой части чисел вида		D
Алгоритм Бриллхарта—Моррисона.		v
					√
Будем обозначать через Pi/Qi подходящие дроби разложения
						n

в непрерывную дробь (чтобы не путать их с элементами факторной

). Факторную базу составляют						p0 = −	1 и простые числа	pi	,
базы {pi}a	a
pi L(n)	= L , где a = const; при этом мы берем лишь те простые
числа, для которых			n	= +1. Алгоритм Бриллхарта—Моррисона ра-
			p
ботает так же как		алгоритмi			Диксона, только вместо случайных зна-

чений m мы берем mi = Pi, и по теореме 3.10 абсолютно наименьший вычет m2i (mod n) равен

Q(mi) = Pi2 − nQ2i ,

√

причем |Q(mi)| < 2 n. В последнем неравенстве и заключается основная идея алгоритма: если в методе Диксона Q(m) < n, то в методе

Бриллхарта—Моррисона |Q(m)| существенно меньше (не превосходит

√

2 n). Следовательно, вероятность того, что Q(m) будет гладким (т. е. разложится в нашей факторной базе), из эвристических соображений значительно выше.

Замечание 3.13. Если p — простое число из факторной базы и p | Q(mi) для некоторого номера i, то p Qi, поскольку (Pi, Qi) = 1.

Тогда Qi2n ≡ Pi2 (mod p), откуда и следует условие			n	= +1.
			p
Приведем оценки сложности алгоритма	Бриллхарта				—	Моррисона,

следуя работе [221]. При получении этих оценок делаются некото-

рые эвристические допущения. Например, предполагают,	что	если
с помощью алгоритма построено 1 + [log2 n] пар (x, y)	таких,	что

x2 ≡ y2 (mod n), то хотя бы для одной из них выполнены неравенства 1 < НОД(x ± y, n).