AOP_Tom2 (1021737), страница 134
Текст из файла (страница 134)
По определению ре(х) = д г(х) = О, р г(х) = да(х) = 1. Докажите, что если р(х) и д(х) являются полиномами, такими, что йек(д) < йеб(д„) и йей(ри-до) < йеб(р ~и-д„~о) для некоторого п > 1, тор(х) = ср„г(х) и д(х) = сд„г(х) для некоторой константы с. В частности, каждый д„(х) является полиномом, "разбивакь щим запигь" (гесогй-Ьгеа51пй) в том смысле, что не существует ненулеиого полинома д(х) меньшей степени, такого, что для любого полинома р(х) полипом р(х) и(х) — д(х) о(х) имел столь же малую степеньь что и р (х) и(х) — д„(х) е(х).
27. [МИ] Предложите путь ускорения деления в(х) на е(х), если заранее известно, что остаток будет нулевым. е4.6.2. Разложение лолииомов на множители Рассмотрим теперь задачу не только поиска наибольшего общего делителя двух или более полиномов, но н разлозгсения полиномов. Разложение по модулю р.
Как н в случае целых чисел (разделы 4.5.2 н 4.5.4), задача разложения представляется существенно сложнее поиска наибольшего общего делителя. Однако разложение полиномов по модулю некоторого простого целого числа р не настачько сложно, как кажется. Гораздо проще найти множители произвольного полинома степени п по модулю 2, чем использовать любой известный метод для поиска множителей произвольного гмбитового двоичного числа. Эта неожиданная ситуация является следствием поучительного алгоритма разложения, открытого в 1967 году Элвином Р. Верлекампом (Е1щуп Н. Всг1е1щгпр) [ВеП Яузсегп ТесЬт'са) Х 46 (1967), 1853-1859]. Пусть р — простое число; все арифметические операции над полиномами в приведенном далее материале выполняются по модулю р.
Предположим, задан полиноы и(х), коэффициенты которого выбраны из множества (О, 1, ..., р — 1). Мы можем считать, что и(х) нормирован. Наша цель — выразить и(х) в виде и(х) = р1 (х)"... р„(х) '", (1) где р1 (х), ..., р„(х) — различные нормированные неприводимые полиномы.
В качестве первого шага можно использовать стандартную технологию определения, ие является ли какой-либо показатель степени е1, ..., е„больше единицы. Если и(х) = и„х" + . + ио = о(х) 1о(У), (2) то производная (найденная так, как обычно, но по модулю р) будет равна и'(х) =пи„х" 1+. +и1 — — 2о(х)о'(х)и1(у)+о(х)2и1'(х), (3) а это выражение кратно о(х). Значит, наш первый шаг в разложении и(х) должен состоять в поиске йсс1(и(х), и'(х)) = е((х). (4) Если д(х) равно 1, то, как мы только что убедились, и(х) свободен ош квадратов, т. е.
представляет собой произведение различных простых р1(х)... р,(х). Если д(х) не равно 1 и д(х) ф и(х), то д(х) является собственным множителем и(х); соотношение между множителями д(х) и множителями и(х)/д(х) ускоряет процегс разложения для этого случая (см. упр. 34 и 36). И наконец, если Ы(х) = и(х), то необходимо, чтобы и'(х) = 0; следовательно, коэффициент и1 при х" ненулевой только тогда, когда й кратно р. Это означает, что и(х) может быть записан как полинам вида о(хв).
В таком случае имеем и(.) = о(х ) = (о(х))". (5) Процесс разложения может быть завершен нахождением неприводимых множителей о(х) и возведением их в степень р. Тождество (5) может показаты:я чизвтелю несколько странным, однако это важный факт, лежащий в основе алгоритма Берлекампа и других методов, которые мы обсудим чуть позже. Его можно доказать следующим образом. Егти о1(х) и о2(х) — некоторые палиномы по модулю р, то (О1(У) +и2(у)) = и1(х) + (1)о1(Х) о2(Х) + ' ' '+ (Г 1)О1(х)О2(У) +О2(Х) о1(у) + и2(у) поскольку биномиальные коэффициенты (г1), ...
„( ' ) кратны р. Далее, если ив произвольное целое число, имеем о" = а (1к1 модулю р) согласно теореме Ферма. Таким образом, когда г(х) = о„,х"' + о„, 1х"' ' + . + се, находим, что о(х)'=(о„х'")" +(о 1х™ ')'+ "+(оо)' — у " + г Х1 1" + .. + о — и(у") Эти замечания показывают, что задача разложения сводится к задаче разложения свободных от квадратов полиномав.
Таким образом, положим, что (6) и(х) = р1(х)ре(х) " .р.(х) является произведением различных простых сомножителей. К какой хитрости следует прибегнуть, чтобы суметь найти р (х), если дан талька и(х)? Идея Берлекампа состоит в применении китайской теоремы об остатках, которая справедлива для полиномов так же, как и для целых чисел (см. упр. 3). Если (вм во,..., в„) является произвольным набором из г целых чисел по модулю р, из китайской теоремы об остатках вытекает, что существует Единственный полянам и(х), такой, что и(х) гн в~ (по модулю р,(х)), ..., и(х) ш в, (по модулю р„(х)), бей(и) < бей(р1) + бей(рт) + + бей(р,) = бей(и). Запись "д(х) ьз 6(х) (по модулю 7(х))', появляющаяся здесь, имеет тот же смысл, что и "д(х) ш 6(х)(по модулю 7"(х) и р)" в упр.
3.2.2-11, поскольку мы рассматриваем полиномивльную арифметику по модулю р. Полинам и(х) в (7) предоставляет способ получения множителей и(х), так как при г ) 2 и в1 ф вт мы получим йсп(и(х), и(х) — в1), делящийся на р1(х), но не на ро(х). Поскольку зти наблюдения показывают, что информацию о множителях и(х) можно получить из соответствующих решений и(х) (7), проанализируем (7) более тщательно. Во-первых, можно заметить, что полипом и(х) удовлетворяет условию и(х) ьз вд = в = и(х) (по модулю р (х)) для 1 < у < а Таким образом, е(х)" св и(х) (по модулю и(х)), бей(и) < бей(и). (8) Во-вторых, имев~си основное полиномивльное тождество х — х = (х — 0)(х — Ц...
(х — (р — 1)) (по модулю р) (9) (см. упр. 6). Следовательно, (х) — е(х) = ( (х) — 0) (е(х) — 1)... (и(х) — (р — 1)) (10) является тождеством для любого полинома и(х) при работе по модулю р. Если е(х) удовлетворяет (8), то и(х) делнт левую часть (10), так что каждый нсприводимый множитель и(х) должен делить один из р взаимно простых множителей правой части (10). Другими словами, все решения (8) должны иметь вид (7) для некоторых вм вт, ..., в,; имеется в точности р' решений (8). Решения е(х) уравнения (8), таким образом, дают ключ к разложению и(х).
Сначала поиск всех решений (8) может показаться более сложным, чем разложение и(х), но в действительности это не так, поскольку множество решений (8) замкнуто по отношению к сложению. Пусть йе8(и) = и. Можно построить матрицу и х п чо,о дол Яо, — 1 1 Яп-ко Ян-ц1 Ял-кл-1 где хв ьз дь „1х" ' + . + дь 1х + дв о (по модулю и(х)) . (12) В таком случае и(х) = и„1х" '+ +е1х+ио является решением (8) тогда и только тогда, когда (ио,им,и -1)9 = (ио е1 .,е -~). (13) Последнее соотношение, в свою очередь, справедливо тогда и только тогда, когда и(х) = ~~~ и ху = ~~~ ~~~ иьщ, ху ьч ~~~ иьхв = и(хв) ьз и(х)в (по модулю и(х)). Значит, алгоритм разложения Берлекампа выглядит следующим образом. В1.Добиться, чтобы и(х) был свободен от квадратов; другими словами, если 8са(и(х), и'(х)) ф 1, свестя задачу к разложению и(х), как указывалось ранее в этом разделе.
В2. Построить матрицу Я, определенную (11) и (12). Это можно сделать одним из двух способов в зависимости от того, очень ли велико р, как поясняется ниже. ВЗ. "Трнангуляризовать" матрицу Я вЂ” 1 где 1 = (б,э.) †единичная матри размера п х и, найти ее ранг п — г и найти линейно независимые векторы и!'),..., и!"), такие, что и!" (ь) — 1) = (0,0,..., О) для 1 < г < г. (В качестве первого вектора и!'! всегда можно взять вектор (1,0,..., 0), представляющий тривиальное решение уравнения (8) и(э)(х) = 1.
Вычишэения могут быть проведены с использованном соответствующих операций со столбцами, как описывается в приведенном ниже алгоритме гл.) В этот момент г равгш количеству непрнводямых множгггелей и(х), потому что решениями (8) являются р' полинамов, соответствующих векторам 1,и(э! + + г„и!"! для всех выборов целых чисел 0 < 1м...,1„< р. Таким образом, если г = 1, то известно, что и(х) непринодим. н на этом работа алгоритма завершается. В4. Вычислить 8сг((и(х),и(з (х) — э) для 0 < в < р, где и(з)(х) — полинам, представленный вектором и(х!. Результатом будет нетривиальное разложение и(х), потому что полинам и!в)(х) — э ненулевой и имеет степень, меньшую, чем г)е8(и).
Согласно упр. 7 имеем и(х) = П 8сг)(и(х) — э,и(х)) (14) в<э<р в случае, если и(х) удовлетворяет (8). Если использование и!')(х) не приводит к разложению и(х) на г множителей, то дальнейшие множители могут быть получены посредством вычисления 8со(и(~)(х) — в, ш(х)) для 0 < э < р и всех найденных множителей и~(х) при й = 3, 4, ..., пока не будут получены все г множителей. (Если в (7) выбрано в; ф в, то получим решение и(х) уравнения (8), которое "отличает" р,(х) от р,(х); некоторый и!")(х) — э будет делиться на р;(х), но не на р,(х), так что в результате этой процедуры в конечном счете будут найдены все множители.) Если р равно 2 нли 3, вычисления на этом шаге весьма эффективны; но если р больше, чем, скажем. 25, то можно использовать гораздо лучший способ, который рассматривается ниже. 1 Исшорическал соринка.
М. Ч. Р. Батлер (М. С. В. Впт!ег) Дивта Х МаГЬ. 5 (1954), 102 107) обнаружил, что матрица Я вЂ” 1, соответствующая свободнолэу от квадратов полинаму с г непринодимыми м~эажителями, будет иметь ранг и — г по модулю р. На самом деле этот факт неявно содержится в более общем результате К. Петра (К. Ре1г) (Саэоргэ рго РбэГогап1 Майэтагйу а Руэйу 66 (1937), 85-94), который определил характеристичоскнй полинам для Я.
См. также Я. Яс)пгагх, ь1иагб Х Ма!!э, 7 (1956), 110 — 124. В качестве примера работы алгоритма В найдем разложение полннома и(х) = хэ э- хэ + 10х~ + 10хз + 8х + 2х + 8 по модулю 13 (этот полинам появляется в ряде примеров в разделе 4,6.1). Быстрое вычисление с использованием алгоритма 4.6.1Е показывает, что Вс!1(и(х), и'(х)) = 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
