AOP_Tom2 (1021737), страница 135
Текст из файла (страница 135)
Таким образом, и(х) свободен от квадратов, и мы возвращаемся к шагу В2. На шаге В2 вычисляется матрица Я, которая в нашем случае представляет собой массив размера 8 х 8. Первая строка Я всегда равна (1, О, О,..., О) и предо~валяет полипом хо шоб и(х) = 1. Вторая строка представляет х'з п!о!1 и(х), и, в общем, х" шод и(х) легко может быть определено следующим образом (для относительно небольших значений 14). Если и(х) =х" +и„!х" !+ +и!х+ио и если х = аь л !х" ! +. + аь !х+ аь о (по модулю и(х)), то х гв аь„!х + +аьлх +а!ох /с+ 1 — л 2 = ак~ !( ил-!х ' ' ' игх ио) + ам~ — ох + ' ' ' + а!ох л — ! = а~+!,„!х + + аг ы !х+ аь.!!,о, где (16) аь„!,, = ас,, ! — аь „!иу, В этой формуле аь ! трактуется как нуль, так что аье!,о = — аь „!ио.
Простая рекуррентность наподобие регистра сдвига (16) упрощает вычисление хешо!(и(х) для к = 1, 2, 3, ..., (п — 1)р. В компьютере такое вычисление в общем случае производится с помощью одномерного массива (а„!,..., а!, ао), а также установок 1+- а„!, а„! 4 — (ал э — Фи„!) шос(Р, ..., а, +- (ао — Фи!) шобР н ао +- ( — 1ио) шеар. (Ыы сталкивались с подобными процедурами в связи с генерированием случайных чисел; см. 3.2.2-(10).) Для используемого в качестве примера полинома и(х) (15), получим такую последовательность коэффициентов х шоб и(х) с использованием арифметики по модулю 13.
й аьл акл 0 0 0 1 0 0 2 0 О 3 0 0 4 0 0 5 0 О 6 0 1 7 1 0 8 0 12 9 12 0 10 0 4 11 4 3 12 3 11 13 11 о а!л ам4 0 0 0 0 0 0 О О 0 1 1 0 0 0 О 0 0 3 3 3 3 2 2 8 8 12 12 10 аед 0 0 0 1 0 0 О 0 3 5 В 0 1 11 аьд 0 0 1 0 0 0 О 0 5 11 0 2 2 7 ан! ако 0 1 1 0 0 О 0 0 0 0 0 0 0 0 О 0 11 5 5 0 2 В 8 0 5 7 1 2 7,11,10,12,5,11). Анало- найти,что 2 1 7 11 3 6 4 3 4 3 6 5 2 11 8 8 6 11 8 6 5 11 7 10 3 3 12 5 10 12 5 0 4 7 1 6 2 3 1 3 2 7 10 0 11 7 0 11 9 (17) 0 0 5 11 7 2 2 3 3 11 10 9 6 12 9 11 0 0 10 12 0 4 1 6 2 1 2 6 0 11 0 11 Этим завершается шаг В2.
На следующем шаге процедуры Берлекампа требуется найти ядро преобразования, осуществляемого матрицей 1~ — 7. В общем, предположим, что А — матрица размера и х п над шлем, ранг которой и — г необходимо определить. Предположим также, что нужно определить линейно независимые векторы пй), Р), ..., поз, такие, что г(ВА = ьй)А = . = и(")А = (0,...,0). Алгоритм для этого вычисления может быть основан на том наблюдении, что любой столбец матрицы А можно умножить на ненулевую величину и что это произведение можно добавить к любому другому столбцу матрицы без изменения ранта матрицы или векторов пр),..., п~") (подобные преобразования равносильны замене матрицы А матрицей АВ, где В представляет собой несингулярную матрицу).
Таким образом, может быть использована следующая хорошо известная процедура "триангуляризации". Алгоритм Х (Алгорипьи ядра). Пусть А — матрица размера п х и, элементы которой а," прин~тлежат полю и имеют индексы в диапазоне 0 < 1, у < и. Этот алгоритм дает г векторов пр) ..,п~"), линейно независимых над полем и удовлетворяющих условию п(ВА = (О,..., 0), где и — г — ранг матрицы А. Х1. [Инициализация.] Установить со +- с~ +- < — с„т < — — 1, г +- О. (Во время вычислений г > 0 будет выполняться только тогда, когда а,, = — 1, а все другие элементы строки с, будут нулевыми.) Х2.
(Цикл по Ц Выполнить шаг ХЗ для й = О, 1, ..., и — 1, затем завершить работу алгоритма. ХЗ. (Проверка зависимости строк.) Если существует некоторое 7' из интервала 0 < у < и, таков, что агу ф 0 и с, < О, то выполнить следующео. Умножить столбец у матрицы А на — 1/аг (так, чтобы аь стало равным — 1), добавить умноженный на ам у-й столбец к 1-му столбпу для всех 1 ф у н наконец установить с, (- к (поскольку, как нетрудно показать, что а,.
= 0 для всех г < Й, эти операции не влияют на строки О, 1, ..., к — 1 матрицы А). Таким образом, второй строкой матрицы Я является (2, 1, гично можно определить хтг тот( и(х), ..., хг' шот) и(х) и 1 0 0 0 0 0 0 0 О О 0 2 0 7 11 3 6 3 3 4 3 6 4 2 11 8 8 6 11 8 6 5 11 7 10 3 3 12 5 0 11 2 3 11 9 12 12 С другой стороны, егли не существует такого г из диапазона 0 < 2 < и, что аьу у1 0 и с, < О, следует установить т+- т+ 1 и вывести вектор = ~на,ом.,.,е„г), )г) определяемый правилом о = 1, еслиг=й; авм еслис,=у>0; (18) 0 в противном случае. 1 Лучше всего механизм работы этого алгоритма проиллюстрировать на конкретном примере.
Пусть А — матрица Я вЂ” 1 из (17) нвд полем целых чисел по модулю 13. При й = О получим вектор дб = (1,0,0, О, О, О, 0,0). При й = 1 на шаге ХЗ можно принять 2 равным О, 2, 3, 4, 5, 6 либо 7; выбор здегь абсолютно произволен, хотя он и повлияет на вид векторов, выдаваемых алгоритмом. При вычислениях вручную удобнее всего взять 2 = 5, поскольку аш — — 12 = — 1. Операции над столбцами на шаге ХЗ преобразуют матрицу А в матрицу 0 0 0 0 0 0 О 0 0 Я 0 0 8 1 4 1 7 5 9 6 6 4 6 12 1 8 9 7 10 6 1 10 1 6 11 9 3 9 6 11 12 2 (Элемент в кружке на пересечении столбца 5 и строки 1 используется здесь для того, чтобы указать, что сь = 1.
Помните, что алгоритм Х нумерует строки и столбцы матрицы, начиная с О, а не с 1,) Когда й = 2, можно выбрать 2 = 4 и аналогично получить следующие матрицы с тем же ядром, что и у Я вЂ” 1. к=2 1с =3 0 0 0 0 0 0 О О 0 0 0 0 0 0 0 О О 0 0 0 0 0 Ог) 0 0 9 9 8 9 1 10 4 11 5 12 12 7 2 7 2 12 0 0 0 Я 0 0 0 О Я 0 0 0 3 11 4 9 10 6 7 1 1 5 9 3 0 5 3 5 4 5 2 5 7 0 3 0 7 0 7 0 6 12 /с = 5 0 0 0 0 0 0 0 0 0 Я 0 0 0 0 Я 0 О 0 О 0 0 0 0 0 1гг) 0 0 0 О 0 0 0 0 5 5 0 9 0 0 11 9 0 10 0 0 0 0 0 О 0 0 0 0 Яг О 0 О 0 1 10 4 8 2 6 1 6 4 0 0 0 О~2 0 0 0 0 0 0 0 О 0 0 Я 4 0 0 11 О 9 0 О 10 0 0 О 0 0 О 8 1 2 4 12 3 0 1 11 6 1=4 0 0 0 0 0 Я2 О 0 0 0 11 4 10 11 11 2 0 0 11 6 3 3 4 11 5 11 1 11 12 3 0 О 5 9 2 11 6 11 0 0 0 О 0 0 О Ю2 0 0 Я 0 5 0 12 9 0 а2 О Я О 0 0 0 0 11 8 8 4 4 0 3 4 6 9 11 11 Теперь каждый столбец, в котором нет элемензв в кружкб, полностью нулевой., так что при !л = 6 и !с = 7 алгоритм дает еще два вектора, а именно: а(~! (О 5 5 0 9 5 1 О) п(з! (О 9 11,9,10,12,0.,1).
Из вида матрицы А после пятого преобразования ясно, что эти векторы удовлетворяют уравнению еА = (О,..., 0). Поскольку вычисление дает три линейно независиллых вектора, и(х) должен иметь ровно три непривадимых множителя. В заключение можно перейти к шагу В4 процедуры разложения. Вычисление 8сс((и(х), и!т!(х) — в) для 0 < в с. 13, где и(в)(х) = хв + 5х' + 9х4 -ь 5хз + 5х, дает хв + 5хв + 9хв + 5х + 5 в качестве отвага при в = О и хз + 8хх + 4х + 12 при в = 2; для остальных значений в бсб равен единице. Таким образом, и!т (х) дает только два из трех множителей.
Обратившись к йсб(ир)(х) — в, х' + 5х~ + 9хз + 5х+ 5), где и!в!(х) = х +12хь+10хв+9хв+11хз+Ох, получим множитель х~+2хв+Зх~+4х+6 для в = 6, х + 3 для в = 8 и единицу в противном случае. Поэтому полное разложение имеет вид и(х) = (х~ + 2х + Зхт + 4х + 6)(хв + Зхз + 4х + 12)(х + 3). (19) Оценим теперь время работы алгоритма Берлекампа при разложении полинома и-й степени по модулю р. Прежде всего, будем считать, что р относительно мало, так что четыре арифметические операции по модулю р, по существу, выполняются за некоторый фиксированный промежуток времени (деление по модулю р может быть преобразовано в умножение путем хранения таблицы обратных величин, как предложено в упр.
9; например, при работе по модулю 13 имеем -' = 7, -' = 9 и т. д.). Для вычислений на шаге В1 необходимо 0(пз) единиц времени; шаг В2 требует 0(рп~) единиц. Для шага ВЗ мы воспользовались алгоритмом Х, которому нужно не более 0(пв) единиц времени. И наконец, на шаге В4 можно увидеть, что вычисление йсь!(7(х),д(х)) по алгоритму Евклида требует 0(с(ей(7) де8(д)) единиц времени.
Следовательно, вычисление йсо(а(з!(х) — в, лп(х)) при фиксированных л и в для всех найденных множителей ю(х) полннома и(х) займет 0(п~) единиц. Шаг В4, звким образом, требует не более 0(реп~) единиц времени. Процедура Берлекампа разлагает на множители по модулю р произвольный полипом степени и за 0(пв + ргпз) шагов при условии, что р — небалыпое простое число; в упр.
5 показано, что среднее количество множителей т примерно равно !пи. Такил| образом, алгоритм Берлекампа гораздо быстрее любого известного метода разложения и-значного числа в системе счисления с основанием р. Конечно. при малых и и р разложение методом проб и ошибок, аналогичное алгоритму 4.5.4А, будет еще более быстрым, чем метод Берлекампа. Из упр. 1 следует. что при малом р стоит отбросить множители малой степени, прежде чем переходить к более сложной процедуре, даже если п велико. При больших р следовало бы испольэовать другую реализацию алгоритма Берлекампа. Деление по модулю р не нужно выполнять прн помощи вспомогательной таблицы обратных чисел.
Вллесто этога, вероятно, следует применять метод из упр. 4.5.2-16, который требует О((!обр)т) шагов. Тогда для шага В1 понадобится 0(п~(!ойр) ) единиц времени, а для шага ВЗ- -О(пз(!ойр) ) единиц. На шаге В2 при большйх р можно вычислить хе шос( и(х) более эффективным способом, чем (16). В разделе 4.6.3 показано, что эту величину можно получить, по сущоству, с помощью 0(!ойр) операций возведения в квадрат по модулю и(х), т. е.
переходов от х~ шоп и(х) к хэь 1пас! и(х), совместно с операциями умножения на х. Операция возведения в квадрат выполняется относительно просто, если сначала создать вспомогательную таблицу значений х'л шастри(х) для гп = и, и+ 1, ..., 2п — 2. Если х шоп и(х) сл ~х + ' ' ' + с1х + се та хэь шоби(х) = (с~ ххл ~+ . + (с,се+с,со)х+с~~) гпос!и(х), где х~" ", ..., х" могут быть заменены полиномами из вспомогательной таблицы. Общее время вычисления х" шоб и(х) сводится к Г)(пэ(!ойр) ) единицам, и мы получаем вторую строку матрицы О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
