состоит в применении китайской теоремы об остатках, которая справедлива для полиномов так же, как и для целых чисел (см. упр. 3). Если (si, зг,..., Sr) является произвольным набором из г целых чисел по модулю р, из китайской теоремы об остатках вытекает, что существует единственный полином v{x), такой, что

v{x) = si (по модулю pi{x)), v{x) = Sr (по модулю Рг{х)), .

deg{v) < cieg(pi) + deg(p2) + • • + deg(pr) = deg(u).

Запись "g{x) = h{x) (no модулю /(x))", появляющаяся здесь, имеет тот же смысл, что и "д{х) = h{x){no модулю f{x) и р)" в упр. 3.2.2-11, поскольку мы рассматриваем полиномиальную арифметику по модулю р. Полином v{x) в (7) предоставляет способ получения множителей и{х), так как при г > 2 и si зг мы получим gcd(u(a;), v{x) - si), делящийся наpi{x), но не наР2{х).

Поскольку эти наблюдения показывают, что информацию о множителях и{х) можно получить из соответствующих решений v(x) (7), проанализируем (7) более тщательно. Во-первых, можно заметить, что полином v{x) удовлетворяет условию vixy = Sj = Sj = v{x) (по модулю Pj{x)) для 1 < J < г. Таким образом,

v{xY = v{x) (по модулю u(a;)), deg(z;) < deg(u). (8)

Во-вторых, имеется основное полиномиальное тождество

х -х = {х- Q){x - 1)... (х - (р - 1)) (по модулю р) (9)

(см. упр. 6). Следовательно,

v{xY - v{x) = {v{x) - 0) {v{x) - 1)... {v{x) - (p - 1)) (10)

является тождеством для любого полинома v{x) при работе по модулю р. Если v{x) удовлетворяет (8), то и{х) делит левую часть (10), так что каждый неприводимый множитель и{х) должен делить один из р взаимно простых множителей правой части (10). Другими словами, все решения (8) должны иметь вид (7) для некоторых si, S2, ..., Sri имеется в точности р решений (8).

Решения v{x) уравнения (8), таким образом, дают ключ к разложению и{х). Сначала поиск всех решений (8) может показаться более сложным, чем разложение и{х), нсЗ в действительности это не так, поскольку множество решений (8) замкнуто по отношению к сложению. Пусть deg(w) = п. Можно построить матрицу п х п

/ 9о,о 90,1 • • • 9о,п-1 \

\ \ ; , (И)

\9п-1,о 9п-1,1 ••• 9п-1,п-1/

= gjfe,„ ia;" Н-----h qk,\x + qkfi (по модулю и{х)). (12)

В таком случае v{x) - z;„ ia:"~ Н-----VviX + vo является решением (8) тогда и только

тогда, когда

{vo,Vi,...,Vn-l)Q = [yo,vi,...,Vn-i). (13)

Последнее соотношение, в свою очередь, справедливо тогда и только тогда, когда

() = = 53 53*9*,> - 51 ла;"* = vix") = v{xY (по модулю и{х)).

Значит, алгоритм разложения Берлекампа выглядит следующим образом.

81. Добиться, чтобы и{х) был свободен от квадратов; другими словами, если gcd[u{x),u{x)) ф 1, свести задачу к разложению «(ж), как указывалось ранее в этом разделе.

82. Построить матрицу Q, определенную (11) и (12). Это можно сделать одним из двух способов в зависимости от того, очень ли велико р, как поясняется ниже.

83. "Триангуляризовать" .матрицу Q - /, где / = (Jjj) -единичная матрица размера п X п, найти ее ранг п - г и найти линейно независимые векторы иЧтакие, что (Q - I) = (О, О,..., 0) для 1 < j < г. (В качестве первого вектора w всегда можно взять вектор (1,0,... ,0), представляющий тривиальное решение уравнения (8) v\x) = 1. Вычисления могут быть проведены с использованием соответствующих операций со столбцами, как описывается в приведенном ниже алгоритме N.) В этот люмент г равно количеству неприводимых множителей и(х), потому что решениями (8) являются р полиномов, соответствующих векторам tifl +•••-!- trV для всех выборов целых чисел О < ti,...,tr < р. Таким образом, если г = 1, то известно, что и{х) неприводим, и на этом работа алгоритма завершается.

84. Вычислить gcd[u{x),v{x) - s) для О < s < р, где уЦх) - полином, представленный вектором г;!]. Результатом будет нетривиальное разложение и{х), потому что полином г;И(х) - S ненулевой и и.меет степень, меньшую, чем deg(w). Согласно упр. 7 имеем

и{х)= П gcd{vix) - S, и{х)) (14)

0<«<р

в случае, если v{x) удовлетворяет (8).

Если использование г;!(a;) не приводит к разложению и{х) на г множителей, то дальнейшие множители могут быть получены посредством вычисления gcd(i;I*)(a;) - s, w{x)) для О < s < р и всех найденных множителей w{x) при fc = 3, 4, ..., пока не будут получены все г множителей. (Если в (7) выбрано Si ф Sj, то получим решение v{x) уравнения (8), которое "отличает" Pi{x) от Pj{x); некоторый уЦх) - s будет делиться на Pi{x), но не на Pj{x), так что в результате этой процедуры в конечном счете будут найдены все множители.)

Если р равно 2 или 3, вычисления на этом шаге весьма эффективны; но если р больше, чем, скажем, 25, то можно использовать гораздо лучший способ, который рассматривается ниже.

Историческая справка. М. Ч. Р. Батлер (М. С. R. Butler) [Quart. J. Math. 5 (1954), 102-107] обнаружил, что матрица Q - I, соответствующая свободному от квадратов полиному с г неприводимыми множителями, будет иметь ранг п - г по модулю р. На самом деле этот факт неявно содержится в более общем результате К. Петра (К. Petr) [Casopis pro Pestovani Matematiky a Fysiky 66 (1937), 85-94], который определил характеристический полином для Q. См. также S. Schwarz, Quart. J. Math. 7 (1956), 110-124.

В качестве примера работы алгоритма В найдем разложение полинома

и{х) =х +х + lQx + 10х + 8а; + 2а; + 8 (15)

по модулю 13 (этот полином появляется в ряде примеров в разделе 4.6.1). Быстрое вычисление с использованием алгоритма 4.6.1Е показывает, что gcd(w(a;), и{х)) - 1. Таким образом, и{х) свободен от квадратов, и мы возвращае.мся к шагу В2. На шаге В2 вычисляется матрица Q, которая в нашем случае представляет собой массив размера 8x8. Первая строка Q всегда равна (1,0,0,..., 0) и представляет полином х° mod «(ж) = 1. Вторая строка представляет х mod «(ж), и, в общем, ж* mod «(ж) легко может быть определено следующим образом (для относительно небольших значений fc). Если

и{х) = ж" + Un-ix"~ Н----+ ЩХ + Uo

и если

х* = afc,„ ia;" Н-----h адж + а,о (по модулю и(х)),

a;*"" = afe,„ ia;" + • • • + адж + ак,ох

= ak,n-i{-Un-ix~-----ЩХ - Uo) + ak,n-2X~ Н-----h ak,oX

= afc+i,n-ia;"~ Н-----h ak+i,ix + ak+i,o,

Uk+ij = Ukj-i - ak,n-iUj. (16)

В этой формуле afe, i трактуется как нуль, так что ак+\,о = -afe,n-iWo- Простая рекуррентность наподобие регистра сдвига (16) упрощает вычисление ж* mod и[х) для fc = 1, 2, 3, ..., (п - 1)р. В компьютере такое вычисление в общем случае производится с помощью одномерного массива (a„ i,..., oi, по), а также установок

t <г- а„ 1, а„ 1 <г- (а„ 2 - tun-\) modp, ..., oi (ао - 1щ) modp

и ао <- (-two) modp. (Мы сталкивались с подобными процедурами в связи с генерированием случайных чисел; см. 3.2.2-(10).) Для используемого в качестве примера полинома и{х) (15), получим такую последовательность коэффициентов X* mod и[х) с использованием арифметики по модулю 13.