(1846), 398-407]. Однако эти работы Гаусса и Галуа опередили свое время и не были поняты, пока Дж. А. Серре (J. А. Serret) не дал детальное толкование несколько позже [Memoires Acad. Sci. Paris, series 2, 35 (1866), 617-688; алгоритм D находится в §7]. Специальные процедуры для разделения fld(i) на неприводимые множители были разработаны последовательно различными авторами, однако универсальный метод, который оставался бы эффективным при больших р, по-видимому, не был открыт до появления компьютеров, потребовавших его разработки. Первый такой рандомизированный алгоритм со строгим анализом времени работы был опубликован Берлекампом [Е. Berlekamp, Math. Сотр. 24 (1970), 713-735]. Он был усовершенствован и упрощен в работах Robert Т. Моепск, Math. Сотр. 31 (1977), 235-250, М. О. Rabin, SICOMP 9 (1980), 273-280, и D. G. Cantor and Н. J. Zassenhaus, Math. Сотр. 36 (1981), 587-592]. Поль Камён (Paul Camion) независимо открыл обобщение для специальных классов полиномов от многих переменных [Comptes Rendus Acad. Sci. Paris A291 (1980), 479-482; IEEE IVans. IT-29 (1983), 378-385].

Среднее количество операций, требующихся для разложения случайного полинома по модулю р, было проанализировано в работе Р. Flajolet, X. Gourdon и D. Panario, Lecture Notes in Сотр. Sci. 1099 (1996), 232-243.

Разложение над кольцом целых чисел. Задача поиска полного разложения полиномов с целыми коэффициентами, когда работа вьшолняется не по модулю р, несколько сложнее предыдущей, но и в этом случае имеется ряд обоснованно эффективных методов решения.

Исаак Ньютон привел метод поиска линейных и квадратичных множителей полиномов с целыми коэффициентами в своей работе Arithmetica Universalis (1707). Его метод был расширен в 1793 году астрономом Фридрихом фон Шубертом (Friedrich von Schubert), который показал, как найти все множители степени п за конечное число шагов [см. М. Cantor, Geschichte der Mathematik 4 (Leipzig: Teubner, 1908), 136-137]. Л. Кронекер (L. Kronecker) независимо открыл метод Шуберта примерно 90 годами позже, но, к сожалению, этот метод крайне неэффективен при п, равном пяти или превышающем пять. Гораздо лучшие результаты могут быть получены при помощи представленных выше методов разложения по модулю р.

Предположим, что нужно найти неприводимые множители полинома

и{х) = и„х" + Un-iX"" -i-----1-Uo, и„фО,

над кольцом целых чисел. В качестве первого шага можно разделить его на наибольший общий делитель коэффициентов полинома; в результате работа будет продолжена с примитивным полиномом. Можно также считать, что и{х) свободен от квадратов (разделив его на gcd(u(x), и(х)), как в упр. 34).

Теперь, если и{х) = v{x)w{x), где каждый из полиномов имеет целые коэффициенты, мы, очевидно, имеем и{х) = v{x)w{x) (по модулю р) для всех простых р, так что существует нетривиальное разложение по модулю р, кроме случая, когда р делит £{и). Эффективный алгоритм разложения и{х) по модулю р может, таким образом, использоваться для того, чтобы попытаться реконструировать возможное разложение и{х) над кольцом целых чисел.

Например, пусть

и{х) = х + х- Зх" - Зх» + 8x2 + 2х - 5. (22)

Мы уже видели в (19), что

и{х) = (х* + 2х + Зх + 4ж + 6)(жЗ + 43. i2)(x + 3) (по модулю 13), (23)

а полное разложение и{х) по модулю 2 показывает наличие двух множителей: одного- степени 6 и другого - степени 2 (см. упр. 10). Из (23) можно увидеть, что и{х) не имеет множителей степени 2, так что он должен быть неприводим над кольцом целых чисел.

Этот частный пример, вероятно, был слишком прост; опыт показывает, что большинство неприводимых полиномов могут быть признаны таковыми путем исследования их множителей по модулю нескольких простых чисел, но установить неприводимость просто удается далеко не всегда. Например, существуют полиномы, такие, что они могут быть корректно разложены по модулю р для всех простых р с согласующимися степенями множителей, но при этом являющиеся неприводимыми над кольцом целых чисел (см. упр. 12).

Большое семейство неприводимых полиномов рассмотрено в упр. 38, а в упр. 27 доказывается, что почти все полиномы являются неприводимыми над кольцом целых чисел. Однако обычно мы не пытаемся раскладывать на множители случайные полиномы; вероятно, есть некоторая причина ожидать наличия нетривиального множителя у полинома, так что нас интересует метод определения множителей тогда, когда они существуют.

В общем случае найти множители и{х), рассматривая разложения w(x) по различным простым модулям, непросто. Например, если и{х) -это произведение четырех квадратичных полиномов, то возникают трудности при согласовании их образов по отношению к различным простым модулям. Поэтому желательно выбрать одно простое число и посмотреть, сколько информации можно получить, используя его, особенно если кажется, что множители по модулю этого простого числа имеют верные степени.

Одна из идей состоит в использовании в качестве модуля очень большого простого числа, достаточно большого для того, чтобы коэффициенты любого корректного разложения и{х) = v{x)w{x) над кольцом целых чисел в действительности находились в диапазоне от -р/2 до р/2. Тогда все возможные целые множители могут быть получены из множителей, вычисленных по известному нам методу по модулю р.

В упр. 20 показано, как получить неплохую оценку границ коэффициентов множителей полинома. Например, если (22) приводимо, то его множитель v{x) имеет степень < 4, а коэффициенты v не превышают 34 согласно результатам этого упражнения. Таким образом, все потенциальные множители и{х) окажутся совершенно очевидными при работе по модулю любого простого числа р > 68. На самом деле полное разложение по модулю 71 равно

(х + 12)(х + 25)(х2 - 13х - 7)(х - 24х - lOx + 31х - 12),

и мы тут же видим, что никакие из полученных полиномов не могут быть множителями (22) над кольцом целых чисел, поскольку постоянные члены не делят 5. Кроме того, никаким образом не удается найти делитель (22), группируя два из полученных множителей, поскольку никакие из найденных постоянных членов 12 х 25, 12 х (-7), 12 X (-12) не равны ±1 или ±5 (по модулю 71).

Определение хороших границ коэффициентов множителей полиномов - нетривиальная задача, поскольку в процессе умножения полиномов может встретиться большое количество сокращений. Например, выглядящий совершенно безобидно полином ж" - 1 имеет неприводимые множители, коэффициенты которых превышают exp(nss") для неограниченно большого количества п. [См. R. С. Vaughan, Michigan Math. J. 21 (1974), 289-295.] Разложению полинома ж" - 1 посвящено упр. 32.

Вместо большого простого числа р, которое может оказаться просто громадным, если и{х) имеет высокую степень или большие коэффициенты, можно также использовать малые р при условии, что и{х) свободен от квадратов по 1кЮдулю р. В этом случае для расширения разложения по модулю р единственным образом в разложение по модулю р" для произвольно большого пиказателя степени е можно воспользоваться важным построением, известным как лемма Хенселя (Hensel) (см. упр. 22). Если применить лемму Хенселя к (23) с р = 13 и е = 2, получится единственное разложение

и{х) = {х- 36)(х - 18x2 + 82х - 66)(х + 54х - Юх + 69х -Ь 84)

(по модулю 169). Обозначив эти множители как v,{х)уз{х)у4{х), мы видим, что ни Vi{x) и г;з(х) не являются множителями и{х) над кольцо.м целых чисел, ни их произведение Vi{x)v3{x) с приведенными по модулю 169 к диапазону (-,) коэффициентами. Итак, мы использовали все возможности доказательства того, что и{х) неприводим над кольцом целых чисел - на этот раз используя только его разложение по модулю 13.

Рассмотренный выше пример нетипичен в одном важном отношении: выполнялось разложение нормированного полинома и{х) из (22), поэтому можно считать, что все его множители нормированы. Что же делать в случае, когда и„ > 1? В такой ситуации старший коэффициент одного из множителей полинома может почти произвольно варьироваться по модулю р; мы, конечно, не хотим рассматривать все имеющиеся возможности. Вероятно, читатель уже заметил эту проблему. К счастью, существует простой выход: разложение и{х) = v{x)w{x) влечет за собой разложение u„u(x) = vi{x)wi{x), где t{vi) = i{wi) = Un = £{u). ("Простите, вы не забыли, что я умножил ваш полином на старший коэффициент перед разложением?") Теперь можно действовать так же, как и выше, с использованием р > 2В, где В ограничивает максимальный коэффициент множителя и„и(ж), а не и{х). Другой путь решения проблемы старшего коэффициента обсуждается в упр. 40.

Объединим весь рассмотренный материал в следующей процедуре.

F1. Найти единственное свободное от квадратов разложение

и{х) = i{u)vi{x).. .Vr{x) (по модулю р),

где р" достаточно велико, как пояснялось выше, и где Vj{x)-нормированный полином. (Это будет возможно для некоторых простых чисел р; см. упр. 23.) Установить также d <- 1.

F2. Для каждой комбинации множителей v{x) = Vi{x).. .Vij{x) с ii = 1, если d - \r, построить уникальный полином v{x) = i{u)v{x) (по модулю р), коэффициенты которого находятся в интервале [-jp*.. р). Если й{х) делит 1{и)и{х), вывести множитель рр(?}(х)), разделить на него и{х), удалить соот-