Cтраница 1
Идея Берлекэмпа состоит в том, чтобы воспользоваться китайской теоремой об остатках, которая справедлива для многочленов точно так же, как она справедлива для целых чисел ( см. упр. [1]
Поэтому эффективный берлекэмпов алгоритм разложения можно использовать, пытаясь по даваемым им ответам по модулю р воссоздать возможное разложение многочлена и ( х) над кольцом целых чисел. [2]
Таким образом, берлекэмпов алгоритм разложения многочленов на простые множители состоит в следующем. [3]
При больших р вычисления, предписываемые алгоритмом Берлекэмпа, обычно выполняют по-другому. Деление по модулю р уже не будет выполняться с помощью вспомогательной таблицы обратных; вместо этого, вероятно, будет использован метод, рассматриваемый в упр. Тогда на выполнение шага В1 потребуется 0 ( 2 () og р) 2) единиц времени; аналогично на выполнение шага ВЗ пойдет О ( n3 ( log р) 2) единиц. [4]
Это утверждение является теоремой 4 в работе Шеннона, Галлаге-раи Берлекэмпа ( 1967) и там же приведено ее доказательство. Однако приведенное там доказательство верно для сформулированной здесь теоремы. [5]
К, ц) ( 243, 22, 1, 2) - граф Берлекэмпа - ван Лин-та - Сейдела. [6]
Найдите полное разложение по модулю 2 многочлена и ( х), заданного формулой ( 21), используя для этого алгоритм Берлекэмпа. [7]
Разумеется, при малых значениях процедура разложения по методу проб и ошибок, аналогичная алгоритму 4.5. 4А, будет работать еще быстрее, чем алгоритм Берлекэмпа. I вытекает, что даже при больших п, прежде чем переходить к более сложным процедурам, стоит сначала выбраковать множители, имеющие малые степени. [8]
Более того, из ( 35) следует, что значения ошибок и их локаторы для констациклических кодов из теоремы 5 могут быть определены с помощью любой процедуры декодирования для БЧХ-ко-дов, такой, как, например, итеративный алгоритм Берлекэмпа [ 2, стр. В частности, когда р - мерсеновское простое число, т.е. когда р 2т - 1 для некоторого целого т, так что операции GF ( p) просто являются арифметикой дополнения единицы, процедура декодирования для р-ичных кодов легко реализуется, в особенности когда с 1 ( циклические коды) или когда с - 1 ( не-гациклические коды), и формирователь синдрома на рис. 2 очень прост. [9]
Первым таким алгоритмом, кажется, был алгоритм Берле-кэмпа [5], 1970 г., для разложения на множители полинома f над полем GF ( p) с р элементами. Алгоритм Берлекэмпа работает полиномиальное время от степени f и logp и с вероятностью по крайней мере 1 / 2 находит неприводимые разложения на сомножители f; в противном случае его работа заканчивается неудачей. Так как алгоритм можно повторять любое число раз и неудачные исходы все независимы, на практике алгоритм всегда разлагает полином за приемлемое ( разумное) время. [10]
Первый метод взят из [ 1, разд. Применяем алгоритм Берлекэмпа [ 8, разд. Если п простое, то такой многочлен h существует и ( h mod п) неприводим ( ср. [11]
Граница Файнстейна была затем уточнена и улучшена Фано [1961], Галлагером [1965], Шенноном, Галлагером и Берлекэмпом [1967] и другими. [12]
Вычисления, выполняемые в шаге В1, осуществляются О ( я2) единиц времени; шаг В2 занимает 0 ( pnz) единиц. В шаге ВЗ мы используем алгоритм N, на выполнение которого тратится самое большее О ( п3) единиц. Наконец, можно заметить, что для определения нод ( / ( я), g ( x)) при помощи алгоритма Евклида требуется О ( deg ( /) deg ( g)) единиц; следовательно, определение нод ( v № ( x) - s, w ( x)) при фиксированных / и s для всех уже найденных делителей w ( х) многочлена и ( х) займет О ( п2) единиц. Шаг В4 поэтому требует не более 0 ( ргп2) О ( рп3) единиц. Итак, разложение на простые множители произвольного многочлена n - й степени по модулю р выполняется алгоритмом Берлекэмпа за 0 ( рп3) шагов, при условии что р-небольшое простое число. Этот метод значительно быстрее любого из известных методов разложения - значных чисел в р-арной системе счисления. [13]