178 Гл. 6. Факторизация многочленов над конечными полями

Как и в случае p > 2, можно доказать, что для случайно выбранного многочлена T = T (x), deg T 2d − 1, наибольший общий делитель f(x) и U(T) будет нетривиален с вероятностью, примерно

равной

1

. Также можно выбирать T (x) среди степеней x, x3, . . . , x2d−1,

2

некоторомj

j, 1 j 2d − 1,

т. е. при

нечетном

наибольший

общий

делитель

(U(x ), f(x)) будет

нетривиален

с

вероятностью, пример-

но равной

1

. Докажем это. Предположим

противное, т. е.,

что

для

2

любогоj

1 j 2d − 1,

либо U(xj) ≡ 0 (mod

нечетного j,

f(x)),

либо

(

≡ 1

(mod f(x))

(использовалась теорема 6.23). Также из теоре

-

U x

2

2

≡ U(T)

(modj

мы

6.23

следует, что U(T ) = U(T)

f(x)). Поэтому для

всех j, 1 j j2d − 1 выполнено сравнение U(x )

≡ 0 (mod f(x))

или

сравнение

U(x ) ≡ 1

(mod f(x)). Так

как

U(T1 + T2) = U(T1) + U(T2),

то

для

любого многочлена

H = H(x) Z/2Z [x],

deg H(x) 2d − 1,

выполнено

сравнение U(H) ≡ 0

(mod f(x))

или

U(H) ≡ 1

(mod f(x)).

Поскольку

мы считаем, что

deg f(x) > d

(если

deg f(x) = d,

то

f(x)

неприводим), то у f(x) есть

два различных неприводимых

делите-

ля f1 (x)

и

f2 (x), deg f1 (x) = deg f2 (x) = d.

Пусть — корень

f2 (x)

в GF(2d).

Поскольку

f2 (x)

неприводим,

то GF(2d) = Z/2Z [ ].

Так

как

deg U(x) = 2d−1,

то

существует

GF(2d),

Для неко-

U( ) = 0.

торого

P(x) Z/2Z [x],

deg P(x) d − 1, справедливо равенство

=

= P( ).

По китайской

теореме об

остатках

построим

многочлен

T = T (x) Z/2Z [x] такой, что

deg T (x) 2d − 1,

T (x) ≡ 0

(mod f1 (x)),

T (x) ≡ P(x)

(mod f2 (x)). Тогда

U(T) ≡ U(0) ≡ 0

(mod f1 (x)), U(T) ≡

≡ U(P(x)) ≡ 0 (mod

f2 (x)), так

как

U( ) = U(P( )) = 0. Однако

это

противоречит тому, что U(T) ≡ 0 (mod f(x))

или U(T) ≡ 1

(mod f(x)).

Полученное противоречие доказывает, что при некотором нечетном j, 1 j 2d − 1, наибольший общий делитель (U(xj), f(x)) будет нетривиален.

§6.5. Некоторые другие усовершенствования алгоритма Берлекэмпа

Вернемся вновь к алгоритму Берлекэмпа, описанному в § 6.3. Ограничимся случаем простого поля Z/pZ.

Пусть p велико. Тогда перебор значений c Z/pZ и вычисление НОД(f(x), h(x) − c) займут много времени. Мы хотим определить множество M Z/pZ, состоящее из тех c, для которых НОД(f(x), h(x) − c) нетривиален.

§ 6.5. Некоторые другие усовершенствования алгоритма Берлекэмпа

179

Первый подход к нахождению множества M заключается в вычислении результанта Res(f(x), h(x) − c). Определение и свойства

результанта можно найти в [9, гл. 5]. Если f(x) = n Aixi Z/pZ [x],

															i=0
m
и h(x) = i=0 Bixi Z/pZ [x], то Res(f(x), h(x) − c) равен определителю
матрицы R размера (n + m)						×	(n + m), где
	0	An . . .						A1			A0				0 . . .				0
An		An−1 . . .						A0				0			. . . . . .	.			0
.	0. . . .	. .	.0. . . . .		......	. .	. .	A. . .	. . .	. A. .		.	. .	. . .	.. .. .. .......	.. .	. .	.A. . . .
R =								n			n−1								0
B B					. . .		B	B−	c			0			. . . . . .	.			0
	0	B		m	. . .					B	0			c	. . . . . .	.			0
								1				−
.	.m. . . .	.	m. .−.1. . .		. . .	. .	. .	0. . .	. . . .	.	.			. . .	. . . . . . .	. . .	.	.	. . . .
	0		0		. . .	. .	. .	. . .	.		B		m		. . . B	1	B	0	c
																			−

Мы видим, что Res(f(x), h(x) − c) является многочленом степени n от переменной c с коэффициентами из Z/pZ. Его корни являются в точности теми значениями c, для которых НОД(f(x), h(x) − c) нетривиален. Поэтому для определения множества M мы находим корни Res(f(x), h(x) − c), как многочлена от c, лежащие в поле Z/pZ; мы можем находить их, например, с помощью вероятностного алгоритма, описанного в § 6.1.

Другой подход к отысканию множества M был предложен Цассенхаузом. Сохраняя введенные выше обозначения, мы предположим дополнительно, что f(x) унитарен, m < n, и что h(x)p ≡ h(x) (mod f(x)).

Тогда
	f(x) =
		НОД(f(x), h(x) − c).	(6.10)
		c M
Обозначим G(y) =			—
	(y − c) Z/pZ [x].

c M

Теорема 6.24. Многочлен f(x) делит G(h(x)); при этом G(y) многочлен минимальной степени среди всех многочленов g(y)Z/pZ [y] \{0} таких, что f(x) делит g(h(x)).

Доказательство. Обозначим через I идеал кольца Z/pZ [y], состоящий из многочленов g(y) таких, что f(x) делит g(h(x)). По определению G(y) I. Кроме того, идеал I является главным, I = (g0 (y)) для некоторого g0 (y) Z/pZ [y] \{0}. Из определения множества M

12*

bjyj, где bk = 1, причем число m —

180		Гл. 6. Факторизация многочленов над конечными полями
и равенства		(6.10) следует, что M = M. Поскольку g0 (y) | G(y),
то g0 (y) =		(y − c) для некоторого подмножества M M.

c M

Применим теорему 6.24 для нахождения M. Пусть |M| = k — неиз-

вестное нам число. Тогда G(y) = k

j=0

минимальное натуральное число, обладающее тем свойством, что многочлены 1, h(x), . . . , h(x)k — линейно зависимы над Z/pZ по модулю многочлена f(x). Тогда мы находим векторы коэффициентов много-

членов h(x)0	(mod f(x)) = 1 = n−1 h0jxj,			h(x)	(mod f(x)) = n−1 h1jxj, . . .
		n−1	j=0			=0
i			j			j
. . . , h(x) (mod f(x)) =		j			первый	номер k, такой,
		hijx , . . ., и берем
		=0
что вектор	(hk,0, . . . , hk,n−1)		линейно	выражается		над Z/pZ через

(h0,0, . . . , h0,n−1), . . . , (hk−1,0, . . . , hk−1,n−1). Это дает нам соотношение

k	k
j
bjh(x)j ≡ 0 (mod f(x)), bk = 1,
=0
с минимальным значением k. Тогда мы полагаем G(y) =	bjyj. Мно-

j=0

жество M будет состоять из всех корней многочлена G(y); мы находим эти корни, например, вероятностными методами из § 6.1.

Еще один метод разложения унитарного многочлена f(x) из кольца GF(q) [x], не имеющего кратных неприводимых множителей, описан в [31, гл. 4, § 2]. Он основан на приведении некоторой эффективно вычислимой с помощью алгоритма Берлекэмпа матрицы A к диагональному виду. Однако сам процесс диагонализации довольно сложен.

В работе [139] предложена вероятностная версия алгоритма Берлекэмпа. С ее помощью можно разложить на множители многочлен из GF(q) [x] степени n в среднем за O((n log n + log q)n(log n)2 log log n) арифметических операций в поле GF(q). В алгоритме был использован метод Видемана для решения систем линейных уравнений над конечными полями (см. об этом гл. 11 далее). Алгоритм Калтофена— Лобо был реализован на компьютере. Многочлены небольшой степени (скажем, до 250) быстрее раскладывать на множители с помощью обычного алгоритма Берлекэмпа, если рассматриваемые поля не слишком велики. Для многочленов высокой степени алгоритм Калтофена— Лобо в ряде случаев оказался эффективным; например, для многочленов степени 10 001 над полем Z/127Z он работает около 102,5 часов на компьютере Sun 4.

§ 6.6. Вероятностный алгоритм проверки неприводимости многочленов

181

§6.6. Вероятностный алгоритм проверки неприводимости многочленов над конечными полями

Пусть p — простое число, p > 2, r N, r 1, q = pr, K = GF(q). Пусть f = f(x) — фиксированный унитарный многочлен из K [x], n = = deg f(x) 2. В данном параграфе мы опишем вероятностный алгоритм проверки неприводимости f(x), аналогичный алгоритму Миллера—Ра- бина для проверки простоты чисел (см. § 1.7).

Обозначим qn − 1 = 2k · t, где t нечетно, R = K [x]/(f) — кольцо из qn

элементов. Если

n

k

|

|

= qn

−

1,

f(x) неприводим, то R является полем,

R

и для любого a

R

\{ }

−1

= a2 t = 1. Извле-

0 выполнено равенство aq

кая квадратный корень, мы получим, что

либо at = 1,

либо at·2j =

−

1 при некотором j,

0

j

< k. (6.11)

Для многочлена f(x) мы обозначим через S множество элементов a R, для которых выполнено условие (6.11).

Теорема 6.25. Если f(x) приводим, то

|S| 12 |R | qn 2− 1 .

Следствие 6.26. Проверяя условие (6.11) для случайно выбранного a R, мы с высокой вероятностью обнаружим, что f(x) приводим. Если же условие (6.11) выполнено для l случайно выбранных элементов a R, то можно считать, что f(x) неприводим с ве-

1

роятностью не меньшей, чем 1 − 2l .

Доказательство теоремы разбивается на два случая.
1	случай. Пусть существует неприводимый многочлен							( )	[ ]
			2					g=g x	K x
такой, что g				| f. Зафиксируем его и обозначим через G множество
	G =	1 + h(x) gf((xx)) (mod f(x)) h(x) K [x], deg h(x) < deg g .
Лемма 6.27.					Справедливы следующие		утверждения:

1.G — подгруппа в R ;

2.для любого h G\1 порядок h равен p;

3.|G| = qm, где m = deg g(x).

Доказательство. Поскольку

1 + h1 gf 1 + h2 gf ≡ 1 + (h1 + h2) gf (mod f),

182 Гл. 6. Факторизация многочленов над конечными полями

то первое утверждение очевидно. Если w G\1, w = 1 + gf , то wp =

	f	p		fp−2		f
= 1 + h			= 1 + hpf				≡ 1 (mod f). Третье утверждение леммы
	g			gp−2		g2
также очевидно.

Лемма 6.28. Если w G\1, то wS ∩ S = .

Доказательство. По лемме 6.27 порядок w равен p, поэто-

му wqn−1 = 1. Если a		S, то aqn−1 = 1, откуда (aw)qn−1 = 1. Значит,
aw S, что и требовалось доказать.
Лемма 6.29. Пусть a, b, G, a = b. Тогда aS ∩ bS = .
Доказательство. aS ∩ bS = тогда и			только тогда, когда S ∩

∩a−1bS = , а последнее равенство верно по лемме 6.28.

Лемма 6.30. Справедливо неравенство

|S| |R |/qm,

где m = deg g.

Доказательство. Обозначим через w1 = 1, w2, . . . , wqm все элементы G R . Тогда множества w1S, . . . , wqm S содержатся в R и не пересекаются по лемме 6.29. Поэтому |R | qm|S|, что и требовалось доказать.

Из леммы 6.30 следует утверждение теоремы 6.25 в рассматриваемом нами случае.

2 случай. Пусть многочлен f бесквадратен, т. е. f = f1 . . . fl, где fi — различные неприводимые многочлены из K [x], и l 2.

Обозначим di = deg fi, Ri = K [x]/(fi) = GF(qdi), i = 1, . . . , l. По китайской теореме об остатках, R изоморфно R1 × . . . × Rl; для элемента

a	m		i ≡ a	(mod	fi	m i	, i =	1, . . . , l. Если m		N,
	R	мы будем обозначать a			)	R
то a		≡ 1 в R тогда и только тогда, когда ai = 1 в Ri, i = 1, . . . , l. По-
этому
		l					l
							i	НОД(m, qdi − 1),
	#{a R | am = 1} =		#{a Ri | am = 1} =
		i=1					=1

так как Ri — циклические группы порядка qdi − 1. Также

#{a R | am = −1} = l #{a Ri | am = −1} =

i=1

= l (#{a Ri | a2m = 1} − #{a Ri | am = 1}) =

i=1

= l (НОД(2m, qdi − 1) − НОД(m, qdi − 1)).

i=1

§ 6.6. Вероятностный алгоритм проверки неприводимости многочленов

183

Поэтому S = S1 S2, где

	l	НОД(t, qdi − 1),
S1 = {a R | at = 1}, |S1| =
	=1
	i
S2 = {a R | at·2k−j = −1 при некотором j, 1 j k},
k	l
|S2| =	(НОД(t2k−j+1, qdi − 1) − НОД(t2k−j, qdi − 1)).
=1 i=1
j
Пусть	qdi − 1 = 2ci bi, i = 1, . . . , l,
где bi — нечетные числа. Очевидно, что при e Z 0
	НОД(2et, 2ci bi) = 2min(e,ci) НОД(t, bi),
	2e НОД(t, b )		при e < ci,
НОД(2e+1t, 2ci bi) − НОД(2et, 2ci bi) = 0		i	при e ci.

Поэтому при c = min(c1, . . . , cl) и при v = min(c, k) выполнено равенство

			v−1		l
			j
			|S2| =		2j НОД(t, bi).
			=0 i=1
Следовательно,			t bi					t bi		2l − 1
|S|	|S1| |S2|	i=1			j=0		i=1
=	+	= l	НОД( , )	1+ v−1		2lj	= l	НОД( , )	1+	2vl − 1	.

Далее,

НОД(qn − 1, qdi − 1) = 2min(k,ci) НОД(t, bi),

откуда

l

i=1

НОД(t, bi) = l	НОД(qn − 1, qdi		− 1)
=1	2min(k,ci)
	l				l
i
		q	di			2min(k,ci)	=
									l
					1)
		(		−					|R | .
	i=1				i=1				i=1 2min(k,ci)

Следовательно,

S 1 +

2vl

−

1

l

R

|

1 +

2vl

−

1

R

|.

l

|

|

| |

2 − 1

i=1 2min(k,ci)

2l − 1

2vl