Таким образом, второй строкой матрицы Q является (2,1,7, И, 10,12,5,11). Аналогично можно определить х" mod и{х), ..., a; mod и{х) и найти, что

(17)

Q-I =

Этим завершается шаг В2. На следующем шаге процедуры Берлекампа требуется найти ядро преобразования, осуществляемого матрицей Q - I. В общем, предположим, что А - матрица размера пхп над полем, ранг которой п - г необходимо определить. Предположим также, что нужно определить линейно независимые векторы ut], «И, иМ, такие, что уЫ = иЫ = ... = г;Н,4 = (О, ...,0). Алгоритм для этого вычисления может быть основан на том наблюдении, что любой столбец матрицы А можно умножить на ненулевую величину и что это произведение можно добавить к любому другому столбцу матрицы без изменения ранга матрицы или векторов г;),..., v (подобные преобразования равносильны замене матрицы А матрицей АВ, где В представляет собой несингулярную матрицу). Таким образом, может быть использована следующая хорошо известная процедура "триангуляри-зации".

Алгоритм N (Алгоритм ядра). Пусть А-матрица размера пхп, элементы которой Oij принадлежат полю и имеют индексы в диапазоне О < i,j < п. Этот алгоритм дает г векторов vK..v\ линейно независимых над полем и удовлетворяющих условию vA = (О,... ,0), где п - г - ранг матрицы А.

N1. [Инициализация.] Установить со ci c„ i <--1, г 0. (Во время

вычислений Cj > О будет выполняться только тогда, когда acj = -1, а все другие элементы строки Cj будут нулевыми.)

N2. [Цикл по fc.] Выполнить шаг N3 для fc = О, 1, ..., п - 1, затем завершить работу алгоритма.

N3. [Проверка зависимости строк.] Если существует некоторое j из интервала О < j < п, такое, что Okj Ф О и Cj < О, то выполнить следу-ющее. Умножить столбец j матрицы А на - l/aj (так, чтобы Okj стало равным -1), добавить умноженный на Oki j-й столбец к г-му столбцу для всех i ф j ж наконец установить Cj +- к (поскольку, как нетрудно показать, что aj = О для всех s < к, эти операции не влияют на строки О, 1, ..., fc - 1 матрицы А).

с другой стороны, если не существует такого j из диапазона О < j < п, что akj ф О и Cj < О, следует установить г г + 1 и вывести вектор

г;М = (vo,vi,...,Vn-i),

определяемый правилом

Vi =

(18)

s, еслис«=>0; если j = fc; I О в противном случае.

Лучше всего механизм работы этого алгоритма проиллюстрировать на конкретном примере. Пусть А - матрица Q-/ из (17) над полем целых чисел по модулю 13. При fc = О получим вектор v = (1,0,0,0,0,0,0,0). При fc = 1 на шаге N3 можно принять j равным О, 2, 3, 4, 5, 6 либо 7; выбор здесь абсолютно произволен, хотя он и повлияет на вид векторов, выдаваемых алгоритмом. При вычислениях вручную удобнее всего взять j = 5, поскольку ois = 12 = -1. Операции над столбцами на шаге N3 преобразуют матрицу А в матрицу

(Элемент в кружке на пересечении столбца 5 и строки 1 используется здесь для того, чтобы указать, что Cs = 1. Помните, что алгоритм N нумерует строки и столбцы матрицы, начиная с О, а не с 1.) Когда fc = 2, .можно выбрать j = 4 и аналогично получить следующие матрицы с тем же ядром, что иу Q - I.

Теперь каждый столбец, в котором нет элемента в кружке, полностью нулевой; так что при fc = 6 и fc = 7 алгоритм дает еще два вектора, а именно:

= (0,5,5,0,9,5,1,0), «И = (0,9,11,9,10,12,0,1).

Из вида матрицы А после пятого преобразования ясно, что эти векторы удовлетворяют уравнению vA = (О,... ,0). Поскольку вычисление дает три линейно независимых вектора, и{х) должен иметь ровно три неприводимых множителя.

В заключение можно перейти к шагу В4 процедуры разложения. Вычисление gcd («(ж), г;И(а;) - s) для О < s < 13, где «И (ж) - + 5х + 9х* + Ъх + 5х, дает х + Ъх + 9х + Ъх + Ъ в качестве ответа при s = О и -Ь 8а; -Ь 4а; -Ь 12 при s = 2; для остальных значений s gcd равен единице. Таким образом, v\x) дает только два из трех множителей. Обратившись к gcd (uf) {х) - s, х -\- бх* -Ь 9х -Ь 5х -Ь 5), где «И (а;) = а; + 12а; + 10а;*+9а; + 11а;2--9а;, получим множитель х--2а;4-Зх--4х--6 для S = 6, а; + 3 для s = 8 и единицу в противном случае. Поэтому полное разложение имеет вид

и{х) = {х* + 2а; + За;= -Ь 4а; + 6)(а; -Ь 83; -Ь 4а; -Ь 12)(х -Ь 3). (19)

Оценим теперь время работы алгоритма Берлекампа при разложении полинома п-й степени по модулю р. Прежде всего, будем считать, что р относительно мало, так что четыре арифметические операции по модулю р, по существу, выполняются за некоторый фиксированный промежуток времени (деление по модулю р может быть преобразовано в умножение путем хранения таблицы обратных величин, как предложено в упр. 9; например, при работе по модулю 13 имеем = 7, = 9 и т. д.). Для вычислений на шаге В1 необходимо 0{v}) единиц времени; шаг В2 требует С>(рп) единиц. Для шага ВЗ мы воспользовались алгоритмом N, которому нужно не более О(п) единиц времени. И наконец, на шаге В4 можно увидеть, что вычисление gcd(/(a;),p(a;)) по алгоритму Евклида требует 0(deg(/) deg{g)) единиц времени. Следовательно, вычисление gcd(i;f(a;) - s, w{x)) при фиксированных j и s для всех найденных множителей w{x) полинома и{х) займет O(n) единиц. Шаг В4, таким образом, требует не более 0{prv?) единиц времени. Процедура Берлекампа разлагает на множители по модулю р произвольный полином степени п за 0{п + рт) шагов при условии, что р - небольшое простое число; в упр. 5 показано, что среднее количество множителей г примерно равно In п. Таким образом, алгоритм Берлекампа гораздо быстрее любого известного метода разложения п-значного числа в системе счисления с основанием р.

Конечно, при малых пир разложение методом проб и ошибок, аналогичное алгоритму 4.5.4А, будет еще более быстрым, чем метод Берлекампа. Из упр. 1 следует, что при малом р стоит отбросить множители малой степени, прежде чем переходить к более сложной процедуре, даже если п велико.

При больших р следовало бы использовать другую реализацию алгоритма Берлекампа. Деление по модулю р не нужно вьшолнять при помощи вспомогательной таблицы обратных чисел. Вместо этого, вероятно, следует применять метод из упр. 4.5.2-16, который требует 0((logp)) шагов. Тогда для шага В1 понадобится 0(n(logp)) единиц времени, а для шага ВЗ - 0(n(logp)) единиц. На шаге В2 при больших р можно вычислить х mod и{х) более эффективным способом, чем (16). В разделе 4.6.3 показано, что эту величину можно получить, по существу.