6.1.2. Общая схема «окольного» метода разложения над кольцом целых чисел

В этом разделе мы дадим краткое описание различных шагов, включенных в «окольный» метод, показанный на рис. 6.1.1; детальное описание некоторых шагов приводится в следующих разделах; см. также (Lazard, 1982; Moenck, 1977) (для случал многих переменных см. (Wang, 1978)).

Предположим, что дан полином , т. е.

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

Разложение на множители полинома получается следующим образом:

где рациональное число 1/2 в этом случае домножается на 2 (содержание второго сомножителя).

В качестве второго примера того же процесса рассмотрим полином . Тогда

Разложение на множители полинома получается следующим образом:

где в этом случае рациональное число умножается на , что соответствует делению на 112 обоих сомножителей и выделению в обоих сомножителях содержания.

Таким образом мы предполагаем, что полином нормирован. (Это ограничение снимается в разд. 6.3.) Ниже излагаются основные шаги «окольного» метода разложения на множители над целыми числами (Musser, 1971, 1975 и 1978):

1. Прежде всего исключаем из нетривиальные сомножители нулевой степени и кратные сомножители, что достигается вычислением наибольших общих делителей в Z и (Другими словами, мы вычисляем примитивный свободный от квадратов полином; читателю следует по этому поводу освежить в памяти разд. 3.2.4.) В качестве результата мы получаем нормированный свободный от квадратов полином где все — различные неприводимые полиномы. Наша цель состоит в вычислении этих q сомножителей

2. Выбираем простое число , такое, что разложение на множители в возможно. Первое требование к выбору числа заключается в том, чтобы полином полученный на шаге 1, имел ту же самую степень и оставался свободным от квадратов по модулю . Поскольку полином нормирован, не делит его старший коэффициент, и, следовательно, степень остается той же самой по модулю ; см. также теорему 3.2.16. Кроме того, мы мажем эффективно проверить, является ли полином свободным от квадратов, проверив равенство обозначает производную полинома Справедливость этого утверждения следует из того, что если , то является кратным полинома Поэтому если , то мы знаем, что свободен от квадратов, в то время как если то нам нужно разложить на множители наконец, если

, то и нам нужно разложить на множители Дальнейшие детали см. в разд. 6.2.1. Размер используемых простых чисел также является существенным фактором при выборе алгоритма разложения в . Применение больших простых чисел сократило бы количество шагов гензелева подъема (описанных в разд. 6.3), необходимых для подъема разложения из до . Однако эффективные алгоритмы разложения на множители в имеются только для малых (Berlekamp, 1970). Третье главное требование к выбору числа — это число сомножителей в полном разложении по модулю . Если неприводимый полином, но по модулю расщепляется на неприводимых сомножителей (для объяснения этого явления см. шаг 3), то в конце подъема мы получаем сомножителей и в итоге подмножеств сомножителей должно рассматриваться на шаге 5, описанном ниже, для определения истинных сомножителей полинома над целыми числами. (Именно из-за этого максимальное время работы алгоритма оказывается экспоненциальным.) Некоторое упрощение задачи получается, если разложить на множители по модулю нескольких простых чисел для которых полином остается свободным от квадратов, и выбрать из них в качестве число, дающее наименьшее число неприводимых сомножителей.

3. Для простого числа , выбранного выше, мы получили разложение на множители в

В разд. 6.2 мы рассматриваем способы получения такого разложения. Заметим, что число q истинных сомножителей полинома над кольцом целых чисел (шаг 1) не обязательно равно числу сомножителей полинома по модулю например, Интересно, что существуют полиномы, неприводимые над целыми числами, которые могут быть разложены на множители по модулю для любого простого . Например, для любых целых чисел а, b и любого простого числа полином разлагается на множители в Чтобы убедиться, что полином разлагается на множители в для любого простого , рассмотрим прежде всего случай Тогда для любых целых чисел а, b имеются следующие четыре возможности: или или

или . Очевидно, что каждый из них приводим по модулю 2. В общем случае, когда — нечетное простое число, выберем с, такое, что . Тогда , и мы имеем три следующие возможности:

Ясно, что для доказательства разложимости по модулю достаточно показать, что хотя бы одно из чисел является квадратом будет тогда разностью двух квадратов]. Пусть d — примитивный корень по модулю (см. теорему 2.3.20). Если не являются квадратами , то , где оба нечетны. Взяв произведение где теперь — четное число, видим, что квадрат . Пусть ; тогда и мы видим, что квадрат . Таким образом, разлагается на множители в по модулю любого простого . Пользуясь критерием Эйзенштейна (теорема 3.2.15), мы легко можем построить полином вида , неприводимый над целыми числами, который разлагается на множители для каждого простого . В качестве примера рассмотрим . В качестве упражнения читателю остается доказательство того, что при полином неприводим над целыми числами.

4. Используя построения гензелева типа (рассматриваемые в разд. 6.3), мы поднимаем полиномы полученные на шаге 3, до соответствующих полиномов таких, что

для достаточно большого положительного целого числа j (это будет разобрано в разд. 6.3). Теперь каждый истинный сомножитель полинома соответствует или отдельному полиному или произведению некоторых из них. Это соответствие выявляется на шаге 5.

5. Здесь мы разбиваем множество полиномов на подмножества , такие, что

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

Анализ времени работы «окольного» метода разложения. Выше мы уже видели, что в худшем случае окольный метод разложения имеет экспоненциальное время работы, поскольку может быть так же велико, как и , и потребуется выполнить большое число пробных делений (а именно ). Однако, как мы сейчас убедимся, в среднем и поскольку среднее значение величины приблизительно равно среднее время вычислений окольного алгоритма полиномиально. (Среднее значение выражения получается с помощью производящих функций и здесь не обсуждается.)

Чтобы убедиться, что рассмотрим эквивалентную задачу определения среднего числа циклов в -перестановках (тот же самый результат может быть получен с помощью производящих функций). Эквивалентность этих задач была установлена в 1880 г. Г. Фробениусом (Knuth, 1981, р. 632).

Таким образом имеет место

Теорема 6.1.1. Среднее число .-циклов в -перестановках равно (не зависит от ).

Локазательство. Пусть с — произвольный фиксированный -цикл. Пусть — любая -перестановка, под действием которой элементы цикла с остаются неподвижными. Пусть с; очевидно, что с является -циклом перестановки с.

Перестановка является взаимно однозначным отображением из множества всех -перестановок на множество всех -перестановок, содержащих цикл с. Поэтому существует

-перестановок, содержащих с в качестве -цикла. Мы можем способами выбрать j элементов -цикла с, затем мажем () способами сформировать из этих j элементов -цикл. Следовательно, число -циклов с равно

В сумме общее число вхождений -циклов во все -перестановки равно

и, разделив его на общее число -перестановок, получаем нужный результат.

Следствие 6.1.2. Среднее число циклов в тг-перестановке равно

где есть гармоническое число, приблизительно равное

Ниже, в разд. 6.2, мы рассмотрим разложение на множители полиномов над конечным полем, а в разд. 6.3 — процесс подъема. [Представляют интерес работы (Butler, 1954; Calmet