Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 27
Текст из файла (страница 27)
Таким образом, г!й(х) дает только два из трек множителей. Обратившись к йсб(с(э!(х) — э, х" + 5х" +9хэ+ 5х+ 5), где с(э (х) = хт+12хэ+1Ох~+йхэ+Пхз+йх, получим множитель ха+2хэ+Зхз+4х+6 для э = 6, х + 3 для э = 8 и единииу в противном случае. Поэтому полное разложение имеет вид и(х) = (х + 2х + Зх + 4х + 6)(х~ + 8х~ + 4х + 12)(х+ 3).
(19) Оценим теперь время работы алгоритма Берлекампа при разложении полинома и-й степени по модулю р. Прежде всего, будем считать, что р относительно мало, так что четыре арифметические операции по модулю р, по существу, выполняются за некоторый фиксированный промежуток времени (деление по модулю р может быть преобразовано в умножение путем хранения таблицы обратных величин, как предложено в упр. 9; например, при работе по модулю 13 имеем -' = 7, -' = 9 н т. д.). Для вычислений на шаге В1 необходимо 0(пэ) единиц времени; шаг В2 требует 0(рп~) единиц.
Для шага ВЗ мы воспользовались алгоритмом Х, которому нужно не более 0(пэ) единиц времени. И наконец, на шаге В4 можно увидеть, что вычисление йсб(у(х),у(х)) по алгоритму Евклида требует 0(с)ей(У) бей(9)) единиц времени. Следовательно, вычисление йсо(с(1)(х) — э, ю(х)) при фиксированных у и а для всех найденных множителей ю(х) полинома и(х) займет 0(пэ) единиц. П1аг В4, таким образом, требует не более 0(ргпв) единиц времени. Процедура Берлекампа разлагает на множители по модулю р произвольный полипом степени п за 0(пз + ргпэ) шагов при условии, что р — небольшое простое число; в упр. 5 показано, что среднее количество множителей г примерно равно !пи. Таким образом, алгоритм Берлекампа гораздо быстрее любого известного метода разложения и-значного числа в системе счисления с основанием р.
Конечно, при малых п и р разложение методом проб и ошибок, аналогичное алгоритму 4.5.4А, будет еще более быстрым, чем метод Берлекампа. Из упр. 1 следует, что при малом р стоит отбросить множители малой степени, прежде чем переходить к более сложной процедуре, даже если и велико. При больших р следовало бы использовать другую реализацию алгоритма Бсрлекалща. Деление по модулю р не нужно выполнять при помощи вспомогательной таблицы обратных чисел. Вместо этого, вероятно, следует применять метод из упр.
4,5.2-16. который требует О((!ойр)") шагов. Тогда для шага В1 понадобится 0(п~(!ойр)~) единиц времени, а для шага ВЗ вЂ” 0(п (!ойр) ) единиц. На шаге В2 при большйх р можно вычислить х" шос) и(х) более эффективным способом, чем (16). В разделе 4.6.3 показано, что эту величину можно получить, по существу, с помощью О(!ойр) операций возведения в квадрат по модулю и(х), т.
е. переходов от х" пюй и(х) к х~~ щой и(х), совместно с операциями умножения на х, Операция возведения в квадрат выполняется относительно просто, если сначала создать вспомогательную таблицу значений х гойи(х) для щ = и, п+ 1, ..., 2п — 2. Если х" пюй и(х) = с„1х" ' + + с1х + со, то х шойи(х) = (с„,х" + ° +(с1се+ с~се)х+со) гойи(х), где хг" з, ..., х" могут быть заменены полиномамн из вспомогательной таблицы. Общее время вычисления хвшойи(х) сводится к О(пз(!ойр)в) единицам, и мы получаем вторую строку матрицы О.
Для получения следующих строк матрицы ц можно вычислить хвг пюй и(х), хвг пюй и(х), ..., выполнив многократное умножение на хг шой и(х) аналогично возведению в квадрат по модулю и(х). Шаг В2 завершается за О(пв(!ойр)з) дополнительных единиц времени, Таким образом, шаги В1-ВЗ требуют в сумме О(пв(!ойр)з + пз(!ойр)т) единиц времени; зти трн шага позволяют получить количество делителей и(х). Но на шаге В4 необходимо вычислить наибольший общий делитель для р различных значений в, что очень сложно даже при умеренно больших значениях р.
Впервые зто препятствие было преодолено Гансом Зассенхаузом (Наив Еаввепйапв) (Х Мшпбег Тйеогу 1 (1969), 291-311], который показал, как определить все "полезные" значения в (см. упр. 14). Еще лучший путь был найден Зассеихаузом н Кантором (Сап1ог) в 1980 году. Если и(х) представляет собой некоторое решение (8), топ(х) делит п(х)в — и(х) = и(х) (и(х)!в '!(в+1) (и(х)<г "!ув — 1). Предполагается, что мы вычисляем 8сй(и(х), "(х)! !~ — 1); (20) при небольшом везении (20) будет нетривиальным множителем и(х). В действительности можно точно определить нужную степень везения, рассмотрев (7). Пусть с(х) гя вз по модулю р (х) для 1 < у < г.
В таком случае р,(х) делит и(х)!в '!г~ — 1 тогда и только тогда, когда в в гв 1 по модулю р. Известно, что в точности (р — 1)/2 целых в в диапазоне 0 < в < р удовлетворяют условию в!" г)~з ш 1 (по модулю р); следовательно, около половины р (х) появятся в 8сй (20). Точнее, если и(х) — случайное решение (8), где все р' решений равновероятны, вероятность того., что 8сй (20) равен и(х), в точности равна ((р — 1)/2р), а вероятностьч что это равно 1, составляет ((р + 1)/2р) .
Вероятность получения нетривиального множителя будет, таким образом, равна -( —,")'-( —.")'= — —,( (:) -"(;) -" )- для всех г > 2 и р > 3. '1аким образом, неплохой идеей является замена шага В4 следующей процедурой (кроме случаев. когдармалб): установить о(х) е- аги!')(х)+ахи! )(х)+.
+а„и!')(х), где коэффициенты а, выбраны случайно в диапазоне 0 < а < р. Пусть текущее частичное разложение и(х) представляет собой и~ (х)... и~(х), где ! изначально равно 1. Вычислим рн(х) = 8сй(и;(х), е(х)!~ !~ — 1) для всех!, текил, что бей(и<) > 1; заменим и,(х) над;(х) (и;(х)/д;(х)) и будем увеличивать значение г после каждого найденного нетривиального йсб. Будем повторять процесс для различных вариантов е(х) до тех пор, пока не получим ! = г.
Если предположить, что потребуется всего 0(1ойг) случайных решений е(х) уравнения ($) (что вполне допустимо), то можно указать верхнюю границу времени, необходимого для выполнения этой альтернативы шагу В4. Она требует 0(гп(!ояр)т) шагов для вычисления е(х), 0(Ф(1ояр)э) шагов для вычисления е(х)!г М~з шоб и;(х) (если Йея(и;) = Ы) и 0(йз(!ойр)з) шагов для поиска йсс((и;(х), и(х)!" '!~э — 1). Таким образом, общее время составляет 0(пэ(1ойр)з 1ойг).
Разложение с различными степенями. Теперь обратимся к несколько более простому пути поиска разложения по модулю р. Изложенные в этол» разделе идеи включают множество поучительных обращений к вычислительной алгебре, н автор не извиняется перед читателем за их количество. Однако проблема разложения по модулю р фактически может быть решена без обращения к множеству концепций. Во-первых, можно использовать тот факт, что неприводимый полипом д(х) степени с( является делителем хг — х и не является делителем хэ' — х лля 1 < с ( И (см. упр. 16).
Таким образом, можно исключить неприводнмые множители каждой степени раздельно, выбрав следующую стратегию. Ш. Исключить квадратные множители, как в алгоритме Берлекампа. Установить также и(х) <- и(х), ю(х) +- "х" и И ~- О (здесь э(х) и а~(х) — переменные, имеющие в качестве значений полиномы).
1зЗ. (Сейчас и~(х) = х" щи с(х); все неприводимые множители е(х) различны и имеют степень > И.) Если и'+ 1 > -' бея(э), выполнение процедуры прекращается, поскольку либо п(х) = 1, либо и(х) — непрнводимый полипом. В противном случае увеличить е' на 1 и заменить ю(х) на ю(х)э щи с(х). ЮЗ. Найти дэ(х) = йсп(и~(х) — х, с(х)).
(Это произведение всех неприводимых множителей и(х), степени которых равны И.) Если дэ(х) ф 1, заменить с(х) на и(х)/дэ(х) и ю(х) на ю(х) щи п(х). Если степень дэ(х) больше, чем и', использовать приведенный ниже алгоритм для поиска его множителей. Вернуться к шагу В2. $ Эта процедура позволяет определить произведение всех непрнводимых множителей со степенью и' и таким образом выяснить, сколько существует множителей конкретной степени.
Поскольку три множителя в нашем примере полинома (19) имеют различные степени, все они могут быть найдены без разложения полиномов дэ(х). Для завершения метода необходим путь, предоставляющий возможность разделить полипом дэ(х) на непрнводимые множители, когда бей(дэ) > П. Майкл Рабин (М!сЬае! ВаЬ!и) в 197б году доказал, что это можно сделать при помощи арифметических операций в поле из р~ элементов. Дзвид Д. Кантор (1)ауЫ О, Сап~от) и Ганс Зассенхауз (Напэ ЕаэзепЬапэ) открыли в 1979 голу, что существует еще более простой путь, основанный на следующем тождестве: если р — некоторое нечетное простое число, то имеем дэ(х) = ясб(дэ(х),!(х)) йсб(дэ(х), Ф(х)!» В~~+1) йсЯда(х), !(х)!г Муэ — 1) (21) для всех полиномов 1(х), поскольку Г(х)г — $(х) кратно всем неприводнмым полиномам степени и' (г(х) можно рассматривать как элемент поля размером р, когда такое поле состоит нз всех полнномов по модулю неприводимого У(х), как в упр.
16). В упр. 29 показано, что йсс)(дэ(х), 1(х)(е'-'Уз-1) будет нетривиальным множителем дэ(х) примерно в половине случаев, если г(х) — случайный полипом степени < 26-1; следовательно. не придется предпринимать множество глучайиык попыток, чтобы найти все делители. Без потери общности можно положить, что 1(х) нормирован, поскольку целые кратные 1(х) не приводят к отличиям, кроме возможного изменения знака г(х)!г -'ут. Таким образом, когда 6 = 1, можно получить 1(х) = х + е, где е выбрано случайно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
