AOP_Tom2 (1021737), страница 137
Текст из файла (страница 137)
Сотр. 24 (1970), 713-735]. Он был усовершенствован и упрощен в работах НоЬегс Т. Моепс1с, МаГЛ. Сагир. 31 (1977), 235 — 250, М. О. НаЪ|п, ЯСОМР 9 (1980), 273 — 280, и Р. О. Сапгог апб Н. 3. Еаввепйаив, Магй. Сотр. 36 (1981), 587-592]. Поль Камеи (Раи! Саппоп) независимо открыл обобщение для специальных классов полиномов от многих йерсменных [Сотргев Непс!ив Асад. Яс!. Рапи А291 (1980), 479-482: 1ЕЕЕ Тгапв.
1Т-29 (1983), 378-385]. Среднее количество операций, требующихся для разложения случайного полинома по модулю р, было проанализировано в рабате Р. Е!а1о!ец Х. Оошбоп и П. Рапапо, Ъесгиге Лосев ш Сотр. Яс!. 1099 (1996), 232-243. Разложение над кольцом целых чисел. Задача поиска полного разложения полиномов с целыми коэффициентами, когда работа выполняется не по модулю р, несколько сложнее предыдущей, но и в этом случае имеется ряд обоснованно эффективных методов ревпения. Исаак Ньютон привел метод поиска линейных и квадратичных множителей полинамов с целыми коэффициентами в своей работе Агййтебса !7п!гегва!!в (1707). Ега метод был расширен в 1793 году астрономом Фридрихом фан Шубертом (Ег!еппсЬ чоп ЯсйиЬегл), который показал, как найти все множители степени и за конечное чицю шагов [см.
М. Сангат, СевсМсйпе г!ег МагЛевпагйй 4 (Ье!рх!8: ТепЬпсг, 1908), 136-137]. аЬ Кронекер (Ь. Кгооес!гег) независимо открыл метод Шуберта примерно 90 годами позже, но, к сожалению, этот метод крайне неэффективен при и, равном пяти или превышающем пять. Гораздо лучшие результаты могут быть получены при помощи представленных выше методов разложения по модулю р. Предположим, что нужно найти непривадимые множители полинома и(х) =и„х" +и„вх" '+. +ив, и„ф0, над кольцом целых чисел. В качестве первого шага можно разделить его на наибольший общий делитель коэффициентов полинома; в результате работа будет продолжена с примитивньлм полиномом.
Можно также считать, что и(х) свободен от квадратов (разделив его на 8са[и(х), и'(х)), как в упр. 34). Теперь, если и(х) = и(х)ш(х), где каждый из полиномов имеет целые коэффициенты, мы, очевидно, имеем и(х) л— а и(х)ш(х) (по модулю р) для всех простых р, так что существует нетривиальное разложение по модулю р, кроме случая, когда р делит г(и). ЭФФективный алгоритм разложения и(х) по модулю р может, таким образом, использоваться для того, чтобы попытаться реконструировать возможное разложение и(х) над кольцом целых чисел. Например, пусть и(х) = хв + х — Зх — Зхв + 8х~ + 2х — 5. (22) Мы уже видели в (19), что и(х) г— а (х~ + 2хэ + Зхэ + 4х + 6)(х' + 8хт + 4х + 12)(х + 3) (по модулю 13), (23) а полное разложение и(х) по моду.по 2 показывает наличие двух множителей: одного — степени 6 и другого — степени 2 (см. упр.
10). Из (23) можно увидеть, что и(т) не имеет множителей степени 2, так что он должен быть неприводим над кольцом целых чисел. Этот частный пример, вероятно, был слишком прост; опыт показывает, что большинство неприводимых полинолгов могут быть признаны таковыми путем исследования их множителей по модулю нескольких простых чисел, но установить неприводимость просто удается далеко не всегда. Например, существуют полиномы, такие, что они могут быть корректно разложены по модулю р для всех простых р с согласующимися степенями множителей, но при этом являющиеся неприводимыми над кольцом целых чисел (см.
упр. 12). Большое семейство неприводимьгх полиномов рассмотрено в упр. 38, а в упр. 27 доказываетгя, что почти все полиномы являются неприводимыми над кольцом целых чисел. Однако обычно мы не пытаемся раскладывать на множители случайные полиномы; вероятно, есть некоторая причина ожидать наличия нетривиального множителя у полинома, так что нас интересует метод определения множителей тогда, когда они существуют. В общем случае найти множители и(т), рассматривая разложения и(х) по различным простым модулям, непросто. Например, если и(х) — это произведение четырех квадратичных полиномов, то возникают трудности прн согласовании их образов по отношению к различным простым модулям.
Поэтому желательно выбрать одно простое число и посмотреть, сколько информации можно получить, используя его, особенно если кажется, что множители по модулю этого простого числа имеют верные степени, Одна из идей состоит в использовании в качестве модуля очень большого простого числа, достаточно большого лля того, чтобы коэффициенты любого корректного разложения и(х) = е(х)ш(х) над кольцом целых чисел в действительности находились в диапазоне от — р/2 до р/2.
Тогда все возможные целые множители могут быть получены и5 множителей, вычисленных по известному нам методу по модулю р. В упр. 20 показана, как получить неплохую оценку границ коэффициентов множителей полинома. Например, если (22) приводимо, то его множитель ь(х) имеет степень (4, а коэффициенты и не превышают 34 согласно результатам этого упражнения.
Таким образом, все потенциальные множители и(х) окажутся совершенно очевидными при работе по модулю любого простого числа р > 68. На самол1 деле полное разложение по модулю 71 равно (х + 12) (х + 25) (хт — 13х — 7) (т4 — 24хэ — 16хг + 31х — 12), и мы тут же видим, что никакие иэ полученных полиномов не могут быть множителями (22) над кольцом целых чисел, поскольку постоянные члены не делят 5. Кроме того, никаким образом не удается найти делитель (22), группируя два из полученных множителей, поскольку никакие из найденных постоянных членов 12 х 25, 12 х ( — 7), 12 х ( — 12) не равны +1 илн ~5 (по модулю 71).
Определение хороших границ коэффициентов множителей полиномов — -нетривиальная задача, поскольку в процессе умножения полиномов может встретиться большое количество сокращений. Например, выглядящий совершенно безобидно полипом х" — 1 имеет неприводимые множители, коэффициенты которых превышают ехр(п'Д" ~"") для неограниченно большого количества п. [См. Н.
С. Ъапй)цш, МкЛР 8ап 51а15.,7. 21 (1974), 289 — 295.) Разложению полинома х" — 1 посвящено упр. 32. Вместо большого простого числа р, которое может оказаться просто громадным, если и(х) имеет высокую степень или большие коэффициенты, можно также использовать малые р при условии, что и(х) свободен от квадратов по модулю р.
В этом случае для расширения разложения по модулю р единственным образом в разложение по модулю р' лля произвольно большого показателя степени е можно воспользоваться важным построением, известным как лемма Хенселя (Непэе1) (см. упр. 22). Если применить лемму Хенселя к (23) г р = 13 и е = 2, получится единственное разложение и(х) = (х — 36)(хэ — 18хэ+ 82х — 66)(х4+ 54х — 10х + 69х+ 84) (по модулю 169). Обозначив эти множители как ~ (х)оз(х)сэ(х), мы видим, что ни с~(х) и еэ(х) не являются множителями и(х) над кольцом целых чисел, ни их произведение е~(х)пз(х) с приведенными по модулю 169 к диапазону ( — э, '~~) коэффициентами.
Итак, мы использовали все возможности доказательства того, что и(х) неприводим над кольцом целых чисел — на этот рвз используя только его разложение по модулю 13. Рассмотренный выше пример нетипичен в одном важном отношении: выполнялось разложение нормированного полинома и(х) из (22), поэтому можно считать, что все его множители нормированы. Что жо делать в случае, когда и„> 1? В такой ситуации старший коэффициент одного из множителей полинома может почти произвольно варьироваться по модулю р', мы, конечно, не хотим рассматривать все имеющиеся возможности. Вероятно, читатель уже заметил эту проблему. К счастью, существует простой выход: разложение и(х) = с(х) ш(х) влечет за собой разложение и„и(х) = с,(х)ш,(х), где 1(с,) = 8(кч) = и„= Г(и).
(" Простите, вы не забыли, что я умножил ваш полином на старший коэффициент перед разложением?") Теперь можно действовать так же, как и выше, с использованием р' ) 2В, где В ограничивает максимальный коэффициент множителя и„и(х), а не и(х). Другой путь решения проблемы старшего коэффициента обсуждается в упр. 40.
Объединим весь рассмотренный материал в следующей процедуре. Р1. Найти единственное свободное от квадратов разложение и(х) = с(и)в~(х)... с,(х) (по модулю р'), где р' достаточно велико, как пояснялось выше, и где су(х) — нормированный полипом. (Это будет возможно для некоторых простых чисел р; см. упр. 23.) Установить также И < — 1. Г2. Для каждой комбинации множителей г(х) = г„(х)...с;,(х) с 1~ — — 1, если -г, построить унвкальный полипом 6(х) э— э 8(и)и(х) (по модулю р'), коэффициенты которого находятся в интервале [ — -'р' ..
-'р'). Если 6(х) делит С(и)и(х), вывести множитель рр[й(х)), разделить на него и(х), удалить соот- ветствующнй гн(х) из списка множителей по модулю р', уменьшить г на число удаленных множителей и завершить работу алгоритма, если Й > йг. 1 Р3. Увеличить Й на 1 и вернуться к шагу Г2, егли Й < зг. ! В заключение этого процесса текущее значение и(х) будет последним непрнводимым множителем изначально заданного полинома. Заметьте, что, если [ив[ < [и„[, предпочтительно выполнять всю работу с "обращенным полиномом" пот" + .
+и„, множители которого представляют собой "обращенные" множители и(х). Описанная процедура требует выполнения условия р' ) 2В, где  — граница коэффициентов любого делителя и„и(х), но можно использовать и гораздо меньшее значение В, если гарантировать, что оно будет верно для делителей степени < -'Йей(и). В этом случае тест на делимость на шаге Г2 должен применяться к ю(х) = п~(х)... о,(х)/п(х), а не к п(х) всякий раз, когда Йей(с) ) -'Йей(и). Можно еще больше снизить В, если гарантировать, что В ограничивает коэффициенты по меншией мере одного корректного делителя и(х) (например, при разложении составного целого Х вместо полинома некоторые делители могут быть очень большими, но хотя бы один из них будет < ~/Л').
Эта идея, предложенная в работе В. Веапхашу, У. Тгет)эап, Р. Б. Жапй, Х ЯугпЬорю Согпр. 15 (1993), 393-413, обсуждается в упр. 21. Проверка делимости на шаге Е2 должна в таком случае быть применена и к п(х), и к ш(х), но вычисления при этом будут выполняться быстрее, так как р' будет иметь гораздо меньшее значение. Описанный авшие алгоритм имеет очевидное слабое место: может возникнуть необходимость в проверке для 2' ~ — 1 потенциальных множителей о(х).
Среднее значение 2" в случайной ситуации составляет порядка и илн, возможно, иг а (см. упр. 5), но в противном случае понадобится ускорить данную часть программы настолько, насколько это скажется возможно. Один из способов быстрого исключения ложных множителей состоит в первоначальном вычислении младшего коэффициента 6(0) с продолжением, только если он делит с(и)и(0). Сложности, рассмотренные в предыдущих абзацах, не возникают, если это условие делимости не выполнено, поскольку такая проверка корректна даже при Йей(о) > — Йей(и). Другой важный способ ускорения процедуры состоит в таком уменьшении г, чтобы оно отражало истинное количество множителей. Алгоритм разложения на различные Степени, приведенный выше, приложим к различным малым простым числам р, Таким образом, для каждого простого числа получается множество Х1д возможных степеней множителей по модулю р„(см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
