Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 28
Текст из файла (страница 28)
Иногда эта процедура будет в действительности успешной для Н > 1, когда используются только линейные полиномы 1(х). Например, имеется восемь неприводимых полиномов 7"(х) степени 3 по модулю 3 и для всех нз ник но-разному вычисляются йсб(7'(х), (х + э)'з — 1) для О < е < 3. 7(х) э=О в=1 э=2 ха+ 2х+1 1 1 1 хз + 2х + 2 7'(х) 7'(х) 7'(х) х~ + х~ + 2 Дх) ((х) 1 хз .1- хт + х + 2 г(х) 1 г(х) хз + хз + 2х + 1 1 У(х) У(х) хз ~- 2хт + ' ! ! ((х) + 2 х т + х + 1 1 1 7 ( х ) хе+ 2хз+2х+2 Дх) 1 1 В упр. 31 частично объясняется, почему линейные полиномы могут оказаться эффективными: однако, когда количество непрнводимых палиномов степени П превышает 2", ясно., что будут существовать неприводимые полииомы, неразличимые посредством линейного выбора г(х).
Альтернатива для (21). которая работает при р = 2, обсуждается в упр. 30, Более быстрый алгоритм разложения с различнымн степенями при очень больших р был найден Э. Калтофеном (Е. Ка)со1еп) и В. Шаупом (У. ЯЬопр); время его работы составляет 0(пэ ь + и'+' !ойр) арифметических операций по модулю р для чисел практяческого размера и О(п!~~ +07" )ойр) таких операций при п -+ оо, когда ы является степенью быстрого" умножения матриц в упр.
4.6.4-66. !См. Х БутЬо)!с Сотр. 20 (1995), 363-397; Л4атЬ. Согпр. 67 (1998), 1179-П97.) Исглоричсскис справки. Идея поиска всех линейных множителей свободного от квадратов полинома 7(х) по модулю р посредством вычисления сна юла д(х) = 8со(хг ' — 1, 7'(х)), а затем — йсб(д(х), (я+э)!' О/э х1) для произвольного е была высказана А.
М. Лежандром (А. М. 1.ейепбге), ЛХйпо!геэ АсаМ. Ясй Раг!е (1785), 484- 490. Поводом к этому послужил поиск всех целых решений Диофантовык уравнений вида 7(х) = рд, т. е. У(х) д 0 (по модулю р). Более общая технология разделения степеней, воплощенная в алгоритме В, была открыла сначала К. Ф. Гауссом (С. Р. Сапээ) до 1800 года, но не публиковалась (см. его 1тегйе 2 (1876), 237), а затем — Эваристом Галуа (Етаг!эте Св)о!э) в классической ныне работе, ставшей основой теории конечных полей (ВийеВп деэ Яс1елсез МагЬетаск!пел, РЬуэ19иеэ ег СЬшидиеэ 13 (1830), 428-435; перепечатана в,7. 6е ЛХагЬ. Ригев ег АррЬдибее 11 (1846), 398-407]. Однако эти работы Гаусса и Галуа опередили свое время и не были поняты, пока Дж. А. Серре (3.
А. Беггес) не дал детальное толкование несколько позже [Метосгея Аеас!. Ясй Рапя, яепея 2, 35 (1866), 617-688; алгоритм П находится в 37]. Специальные процедуры для разделения дя(х) на нелриводимые множители были разработаны последовательно различными авторами, однако универсальный метод, который оставался бы эффективным лри больших р, ло-видимому, не был открыт до появления компьютеров, потребовавших его разработки. Первый такой рандомизированный алгоритм со строгим анализом времени работы был опубликован Берлекампом [Е. Вег!е!сашр, Масй. Сошр.
24 (1970), 713-735]. Он был усовершенствован и упрощен в работах НоЬегс Т. Моепс)с, Май. Сотр. 31 (1977), 235-250, М. О. ВаЬ|п, 81СОМР 9 (1980), 273-280, и П. О. Сапсог апс! Н. 3, ЕаяеепЬаия, Масй. Сошр. 36 (1981), 587-592]. Пс ль Камеи (Раи! Сапиоп) независимо открыл обобщение для специальных классов лолиномов от многих переменных [Согпрсея Неис)ия Асад. Вс!. Раг!я А291 (1980), 479-482; 1ЕЕЕ Тгала 1Т-29 (1983), 378-385].
Среднее количество операций, требующихся для разложения случайного полинома по модулю р, было проанализировано в работе Р. Р!а)о!ес, Х. Ооигс)оп и П. Рапапо, Еесеиси 1!осея 1п Сотр. Яс!. 1099 (1996), 232-243. Разложение над кольцом целых чисел. Задача поиска полною разложения полиномов с целыми коэффициентами, когда работа выполняется не ло модулю р, несколько сложнее предыдущей, но и в этом случае имеется ряд обоснованно эффективных методов решения.
Исаак Ньютон привел метод поиска линейных и квадратичных множителей полиномов с целыми коэффициентами в своей работе Апйслейса Плп егяайя (1707). Его метод был расширен в 1793 году астрономом Фридрихом фон Шубертом (гг!ес!г!сЬ гоп 8сЬиЬегс), который показал, как найти все множители степени л за конечное число шагов [см. М.
Сапсог, СеясЬ!сЬсе с)ег Масйеспасй 4 (1 е!рг!8: ТеиЬлег, 1908), 136-137]. Л, Кронекер (1. Кгопес!сег) нелавсссимо открыл метод Шуберта примерно 90 годами позже, но, к сожалению, этот метод крайне неэффективен лри и, равном пяти или превышающем лять. Гораздо лучшие результаты могут быть получены при помощи представленных выше методов разложения ло модулю р. Предположим, что нужно найти неприводнмые множители лолннома и(х) =и„х" +и„>х" '+ +ие, и„~0, нэд кольцом целых чисел. В качестве первого шага можно разделить его на наибольший общий делитель коэффициентов полннома: в результате работа будет продолжена с лримитияньсм полиномом, Можно также считать, что и(х) свободен от квадратов (рвзделив его на йсс! [и(х), и'(х)), как в упр.
34). Теперь, если и(х) = и(х) се(х), где каждый из полнномов имеет целые коэффициенты, мы, очевидно, имеем и(х) ээ и(х)ш(х) (ио модулю р) для всех простых р, так что существует нетривиальное разлсокение по модулю р, кроме случая, когда р делит С(и). Эффективный алгоритм разложения и(х) ло модулю р может, таким образом, использоваться для того, чтобы попытаться реконструировать возъюжное разложение и(х) над кольцом целых чисел. Например, пусть „(х) хэ + хе 3х4 3хэ + 8хг + 2х (22) Мы уже видели в (19), что и(х) =- (х~ + 2хз + Зхг + 4х+ 6)(хз + 8хг + 4х + 12)(х + 3) (по модулю 13), (23) а полное разложение и(х) по модулю 2 показывает наличие двух множителей: одного — степени б и другого — степени 2 (см.
улр. 10). Из (23) можно увидеть, что и(х) не имеет множителей степени 2, так что он должен быть неприводим над кольцом целых чисел. Этот частный пример, вероятно, был слишком прост; опыт показывает, что большинство неприводимых полнномов могут быть признаны таковыми путем исследования их множителей по модулю нескольких простых чисел, но установить неприводимость просто удается далеко ие всегда Например, существуют полиномы, такие, что они могут быть корректно разложены по модулю р для всех простых р с согласующимися степенями множителей, но при этом являющиеся непрнводнмымн над кольцом целых чисел (см. упр. 12). Большое семейство неприводимых лолиномов рассмотрено в упр.
38, а в упр, 27 доказывается, что почти все полнномы являются неприводимыми над кольцом целых чисел. Однако обычно мы не пытаемся раскладывать на множители случайные полиномы; вероятно, есть некоторая причина ожидать наличия нетривиального множителя у полинома, так что нас интересует метод определения множителей тогда, когда они существуют. В общем случае найти множители и(х), рассматривая разложения и(х) по различным простым молулям, непросто. Например, если и(х) — это произведение четырех квадратичных полиномов, то возникают трудности лри согласовании их образов по отношению к различным простым модулям.
Поэтому желательно выбрать одно простое число и посмотреть, сколько информации можно получить, используя его, особ~лип есл«паж~тек, что множители ло модулю этого простого числа им~юг верные степени. Одна из идей состоит в использовании в качестве модуля очень большого простого числа, достаточно большого для того, чтобы коэффициенты любого корректного разложения и(х) = о(х) ю(х) пад кольцом целых чисел в действительности находились в диапазоне от -р~2 до р/2.
Тогда все возможные целые множители могут быть получены из множителей, вычисленных по известному нам методу по модулю р. В упр. 20 показано, как получить неплохую оценку границ коэффициентов множителей полинома. Например, если (22) пряводимо, то его множитель о(х) имеет степень < 4, а коэффициенты и не превышают 34 согласно результатам этого упражнения, Таким образом, все потенциальные множители и(х) окажутся совершенно очевидными при работе по модулю любого простого числа р > 68. На самом деле полное разложение по модулю 71 равно (х + 12)(х + 25)(х~ — 13х — 7)(х~ — 24хз — 16х + 31х — 12), и мы тут же видим, что никакие из полученных полнномов не могут быть множителямн (22) над кольцом пелых чисел, поскольку постоянные члены не делят 5, Кроме того, никаким образом не удается найти дешитешь (22), группируя два из полученных множителей, поскольку никакие из найденных постоянных членов 12 х 25, 12 х (-7), 12 х ( — 12) не равны х1 или х5 (по модулю 71).
Определение хороших границ коэффициентов множителей полиномов — нетривиальная задача, поскольку в процессе умножения полиномов может встретиться большое количество сокращений. Например, выглядящий совершенно безобидно полинам х" — 1 имеет неприводнмые множители, коэффициенты которых превышают екр(ц'Де'к") для неограниченно большого количества и.
(См. Н. С. Ъапйпап, ЛХИи8ап ЛйаНь Х 21 (1974), 289-295.) Разложению полннома х" — 1 посвящено упр, 32. Вместо большого простого числа р, которое может оказаться просто громадным, если и(х) имеет высокую степень или большие коэффициенты, можно также использовать малые р при условии, что и(х) свободен от квадратов по модулю р. В этом случае для расширения разложения по модулю р единственным образом в разложение по модулю р' для произвольно большого показателя степени е можно воспользоваться важным построением, известным как лемма Хенселя (Непэе)) (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
