Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 26
Текст из файла (страница 26)
(8) Во-вторых, имеется основное полиномиальное тождество х" — * ьв (х — 0)(х — 1)... (х — (р — 1)) (по модулю р) (0) (см. упр. 8). Следовательно, (х)" - (.) = ( (*) - 0)( (.) - 1) ( (*) - (. — )) (10) является тождеством для любого полинома е(х) прн работе по модулю р. Если е(х) удовлетворяет (8), то и(х) делит левую часть (10), так что каждый неприводимый множитель и(х) должен делить один из р взаимно простых множителей правой части (10), Другими словами, все решения (8) должны иметь вид (7) для некоторых в1, вв, ..., в„; имеется в точности р" решений (8).
Решения е(х) уравнения (8), таким образом, дают клсоч к разложению и(х). Сначала поиск всех решений (8) может показаться более сложньсм, чем разложение и(х), но в действительности зто не так, поскольку множество решений (8) замкнуто по отношению к сложению. Пусть ссе8(и) = п.
Можно построить матрицу и х и ЧО,О ЧО,1 ЧО,~-1 1 Ч -1,О Чо-1,1 Чо-с,о-1 х»в вз чв,о 1х" '+" + чвлх+ чмо (по модулю и(х)). (12) В таком случае е(х) = и„сх" '+ +ос х+ео является решением (8) тогда и только тогда, когда (ЕО~Е1, ° ° ° био-1)9 = (ЕО Щ~ ° °,ио-1) (13) Последнее соотношение, в свою очередь, справодливо тогда и только тогда, когда е(х) = ~ ивх~ = ~~1 ~~1 евчк х~ ш ~евх»» = е(х») вя и(х)» (по модулю и(х)). 1 у в в Значит, алгоритм разложения Берлекампа выглядит следующим образом.
В1. Добиться, чтобы и(х) был свободен от квалратов; другими словами, если йсг)(и(х), и'(х)) Ф 1, свести задачу к разложению и(х), как указывалось ранее в этом разделе. В2. Построить матрнпу С, определенную (11) и (12). Это можно сделать одним из двух способов в зависимости от того, очень лн велико р, как поясняется ниже. ВЗ. "Триангуляризовать" матрицу Я вЂ” 1, где У = (30) — единичная матрица размера и х и, найти ее ранг и — г н найти линейно независимые векторы а(~),...., гИ, такие, что аВ) (ь) — Г) = (О,О,..., 0) для 1 < у < г.
(В качестве первого вектора а(В всегда можно взять вектор (1,0,..., 0), представляющий тривиальное решение уравнения (8) а(В(х) = 1. Вычисления могут быть проведены с использованием соответствующих операций со столбцами, как описывается в приведенном ниже алгоритме Х.) В этот момент г ранна количеству непрнводнмых множителей и(х), потому что решениями (8) являются р" полиномов, соответствующих векторам 1га(О + ° + 1„д"~ для всех выборов целых чисел 0 < гг,...,1, < Р. Таким образом, если г = 1, то известно, что и(х) неприводим, н на этом работа алгоритма завершается. В4. Вычислить 8сг((и(х),аРО(х) — в) для 0 < в < р, где н(э)(х) — полинам, представленный вектором Ф).
Результатом будет нетривиальное разложение и(х), потому что полипом а(э) (х) — в ненулевой и имеет степень, меньпгую, чем аей(и). Согласно упр. 7 имеем и(х) = П йсг)(г(х) -в, и(х)) (14) 0<в<в в случае, если а(х) удовлетворяет (8). Если использование а("')(х) не приводит к разложению и(х) на г множителей, то дальнейшие множители могут быть получены посредством вычисления йсгг(н(в)(х) — з, ю(х)) для 0 < з < р и всех найдеггных множителей ш(х) при й = 3, 4, ..., пока не будут получены все г множителей.
(Если в (7) выбрано з; ф з, то получим решение е(х) уравнения (8), которое "отличает" р;(х) от р,(х); некоторый а~ )(х) — з будет делиться на р;(х), но не на р.(х), так что в результате этой процедуры в конечном счете будут найдены все множители.) Если р равно 2 или 3, вычисления на этом шаге весьма эффективны; но если р больше, чем, скажем, 25, то можно использовать гораздо лучший способ, который рассматривается ниже. $ Исгларическал справка.
М. Ч. Р. Батлер (М. С. В.. ВцВег) (Цингой. Х Май. 5 (1954), 102-107) обнаружил, что матрица Я вЂ” У, соответствующая свободному от квадратов палимому с г неприводимыми множителями, будет иметь ранг и — г по модулю р. На самом деле этот факт неявно содержится в более общем результате К. Петра (К. Регг) (Сззоргз рго Рззгогапу Магетаггку а Рузгку 66 (1937), 85-94), который определил характеристический полинам для Я. См.
также Я. Яс)гъагх, Цинги Х Маг)г. Т (1956), 110-124. В качестве примера работы алгоритма В найдем разложение полннома и(х) = х'+х'+ 10х'+ 10х'+йх'+ 2х+8 (15) по модулю 13 (этот полинам появляется в ряде примеров в разделе 4.6.1). Быстрое вычисление с использованием алгоритма 4.6.1Е показывает, что йсг((и(х) „и'(х)) = 1. Таким образом, и(х) свободен от квадратов, и мы возвращаемся к шагу В2.
На шаге В2 вычисляется матрица ф которая в нашем случае представляет собой массив размера 8 х 8. Первая строка Я всегда равна (1, О, О,..., 0) и представляет полинам хо шог( и(х) = 1, Вторая строка представляет х'з пюб и(х), и, в общем, хь шод и(х) легко может быть определено следующим образом (дчя относительно небольших значений )г). Если и(х) = х" + и„,х"-' + " + и,х + ио Х" атаев 1Х" '+ .+ак1Х+аьд (ПО МОДУЛЮ и(Х)), х ги ае, гх + + амгх + амох о+1 — о 1 ГЯ ао,е-1(-и„-1Х" ' — ° — и1Х вЂ” иО) + аме аХ" + ° +аЬЛХ =по+1,„1х + +оо+1лх+по+1,о. о-1 (16) аь+13 = акз-1 — ае,„-гиг.
В этой формуле аь, 1 трактуется как нуль, так что аь+1,о = — ак, 1ио. Простая рекуррентность наподобие регистра сдвига (16) упрощает вычисление хо пкк1 и(х) для й: 1, 2, 3, ..., (и — 1)р. В компьютере такое вычисление в общем случае производится с помощью одномерного массива (а„1,..., аг „ао), а также установок 1+- а„1, а -1 <- (а„з — Фи„1) пюг( р, ..., аг +- (ао — 1и1) шог(р и ао +- (-1ио) шог(р. (Мы ствлкивалнсь с подобными процедурами в связи с генерированнем случайных чисел; см.
3.2.2-(1О).) Для используемого в качестве примера полинома и(х) (15), получим такую последовательность коэффициентов х~ шод и(х) с использованием арифметики по модулю 13. 7г о 1 2 3 4 5 6 7 6 9 1О 11 12 13 акг амо о о о о о о о о о о о о а 1 О О 12 12 О О 4 3 3 11 11 5 аьл аьл амз о а а о о о а о о о о а 1 о о о а о а о о о О 3 3 3 3 5 3 2 5 2 6 а 8 12 12 1О 11 аьл аьл ако о о О 1 О о о о о о о о о о о а о о о о а о 5 П 5 И 5 О О 2 5 2 В О 2 5 7 7 1 2 7,11,10,12,5,11), Анало- найти, что Таким образом, второй строкой матрицы гично можно определить х~е пюб и(л), 1 0 0 2 1 7 3 6 4 4 3 6 2 11 8 б 11 8 5 11 7 3 3 12 (17) 0 0 0 0 0 2 О 7 11 10 3 6 3 3 0 4 3 6 4 1 2 П 8 8 2 6 11 8 6 2 5 11 7 10 0 3 3 12 5 0 0 0 0 12 5 11 4 7 2 6 2 3 1 3 11 6 10 9 11 6 12 11 9 11 Этим завершается шаг В2. На следующем шаге процедуры Берлекампа требуется найти ядро преобразования, осуществляемого матрицей Я вЂ” Х.
В общем, предположим, что А — матрица размера и х и над полем, ранг которой и — г необходимо определить. Предположим также, что нужно определить линейно независимые векторы оР) г(э), е"), такие„что и(ОА = ей)А = " = гр)А = (0,...,0). Алгоритм для этого вычисления может быть основан на том наблюдении, что любой столбец матрицы А можно умножить на ненулевую величину и что это произведение можно добавить к любому другому столбцу матрицы без изменения ранга матрицы или векторов нр),..., и(6 (подобные преобразования равносильны замене матрицы А матрицей АВ, где В представляет собой несннгулярную матрицу), Таким образом, может быть использована следующая хорошо известная процедура "триангуляризации". Алгорнть1 Х (Алеоритим ядра). Пусть А — матрица размера и х и, элементы которой а„принадлежат полю и имеют индексы в диапазоне 0 < 1, у < и.
Этот алгоритм дает г векторов ор)... о("), линейно независимых над полем и удовлетворяющих условию е(ВА = (О,..., 0), где и — г — ранг матрицы А. Х1. (Инициализация.) Установить се с- с~ +- "° +- с„~ е- -1, г +- О. (Во время вычислений с > 0 будет выполняться только тогда, когда а,,~ = — 1, а все другие элементы строки с будут нулевыми.) Х2. [Цикл по 5.) Выполнить шаг МЗ для й = О, 1, ..., п-1, затем завершить работу алгоритма. ХЗ.
(Проверка зависимости строк.) Если существует некоторое у из интервала 0 < у < и, такое, что аь1 ф О и с- < О, то выполнить следующее. Умножить столбец у матрицы А на -1/аьг (так. чтобы агн стало равным -1), добавить умноженный на аы ~-й столбец к 1-му столбцу для всех 1 ф у и наконец установить с; <- й (посколькУ, как нетРУдно показать, что агз = 0 длЯ всех в < й, эти операции не влиявзт на строки О, 1, ..., й — 1 матрицы А). Я является (2, 1, , хэг шос) и(х) и О 0 Р 0 11 10 12 5 3 0 4 7 5 1 6 2 8 3 1 3 6 2 7 10 10 О 11 7 5 0 11 9 0 11 2 3 11 9 12 12 С другой стороны, если не существует такого у' из диапазона 0 < у < и, что азу 14 О и с.
< О, следует установить г +- г + 1 и вывести вектор (ее~е1г.. ~еэ-г)> И ( определяемый правилом 1, еслиуюй; пю, если с, = у > 0; (18) О в противном случае. ! Лучше всего механизм работы этого алгоритма проиллюстрировать на конкретном примере. Пусть А — матрица Я- Х из (17) над полем целых чисел по молулю 13. При 5 = 0 получим вектор ир) = (1, О. О,О, 0,0,0,0). Прн 5 = 1 на шаге ХЗ можно принять у равным О, 2, 3, 4, 5, 6 либо 7; выбор здесь абсолютно произволен, хотя он и повлияет на вид векторов, выдаваемых алгорятмом. При вычислениях вручную удобнее всего взять у = 5, поскольку аы = 12 = -1.
Операции нвд столбцами на шаге ХЗ преобразуют матрицу А в матрицу О О 0 О 0 О 0 0 о о о 11 6 5 3 3 9 4 11 2 5 11 11 б 12 ЗИ (Элемент в кружк4 на пересечении столбца 5 и строки 1 используется здесь лля того, чтобы указать, что сэ — — 1, Помните., что алгоритм Х нумерует строки и столбцы матрицы, начиная с О, а не с 1.) Когда 5 = 2, можно выбрать у' = 4 и аналогично получить следующие матрицы с тем же ядром, что н у Я вЂ” У.
яж2 5=3 О О 0 0 0 О 0 О О 0 0 0 О 0 О О 0 Я О О 0 Я 0 0 О О 0 0 0 О 9 11 8 8 5 11 4 4 0 О 7 3 4 6 7 12 9 11 П 2 О 0 0 0 Я О 0 О 0 0 (ш) 0 0 О 1 3 П 4 9 10 б 4 7 1 1 5 9 3 3 0 5 3 5 4 5 1 2 5 7 О 3 О 6 7 О 7 О 6 12 0 0 О 0 0 0 0 О О 0 Ц$0 0 О О 1 10 4 8 2 6 1 6 4 О 0 О 8 2 12 0 11 я=4 0 0 0 0 0 Я О (Сз) О 0 О О 0 О 0 11 4 4 10 11 П 11 2 0 0 0 О О 0 0 0 О О Я О О 0 9 О 10 о о а о о 8 1 4 1 7 5 9 6 б 4 6 12 1 8 9 7 10 6 1 10 1 6 П 9 3 9 6 П 12 2 0 0 О О 0 О 0 Я О 9 9 8 1 10 4 5 12 12 2 7 2 0 0 О 0 0 О 0 О О 0 Я 0 0 0 0 (шз) О О 5 О О 12 9 О 5=5 О 0 0 0 0 Я О О 0 О О 0 О 5 О 11 0 0 О (Сз) 0 0 0 О 0 0 0 О О О Я 0 0 0 5 О 9 9 0 10 Теперь каждый столбец, в котором нет элемента в кружке, полностью нулевой: так что при х = 6 н я = 7 алгоритм дает еще два вектора, а именно: е( ! = (О, 5, 5, О, 9, 5, 1, О), е! ! = (О, 9, П, 9, 10, 12, О, 1).
Из вида матрицы А после пятого преобразования ясно, что эти векторы удовлетворяют уравнению вА = (О,...,О). Поскольку вычисление дает три линейно независимых вектора, и(х) должен иметь ровно трн неприводимых множителя. В заключение можно перейти к шагу В4 процедуры разложения. Вычисление йсп(и(х), п(э)(х) — э) для О < э < 13, где е!э!(х) = хе + Зх~ + 9х" + 5х- + 5х, дает хе +5х" + 9хэ+ 5х+5 в качестве ответа при в = О н ха+ 8хз+ 4х+12 при э = 2; для остальных значений э йсг! равен единице.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
