проще старших, необходимо применить эту процедуру к "обращенным" полиномам u{x),v{x) и обратить полученный результат.

Полиномы от многих переменных. Подобные методы приводят к алгоритмам, применимым для разложения на множители или поиска наибольших общих делителей полиномов от нескольких переменных с целыми коэффициентами. С полиномом u{xi,xt) удобно работать по модулю неприводимых полиномов Х2- ог,..., xt- at, играющих в данном случае роль р из рассматривавшегося ранее материала. Поскольку v{x) mod (х-а) = v(a), значение u{xi,. ..,xt) mod {жг -a2,...,xt - at} является полиномом от одной переменной u{xi, ог,..., at). Если целые числа ог,..., а< выбраны так, что ог, ...,at) имеет ту же степень xi, что и исходный полином u(xi,X2,.. .,Xt), подходящее обобщение построения Хенселя "поднимет" свободные от квадратов разложения этого полинома от одной переменной к разложениям по модулю {{х2 - аг)", {xt- at)"}, где Uj -степень Xj в u. В то же время можно работать и по модулю подходящего целого простого числа р. Чтобы сохранялась разреженность промежуточных результатов, как можно большее количество aj должно быть нулевым. Дополнительная информация приводится в упоминавшейся в этом разделе статье, а также в Р. S. Wang, Math. Сотр. 32 (1978), 1215-1231.

Со времен первых пионерских статей, процитированных выше, накоплен значительный вычислительный опыт. Для ознакомления с ним рекомендуется обратиться к работе R. Е. Zippel, Effective Ро/ynomia/ Computation (Boston: Kluwer, 1993), в которой приведен обзор последних важных публикаций. Кроме того, в настоящее время возможно разложение полиномов, даваемых неявно вычислительной процедурой "черного ящика" даже если они, будучи записанными явным образом, заполнят всю Вселенную [см. Е. Kaltofen and В. М. Trager, J. SymboUc Сотр. 9 (1990), 301-320; Y. N. Lakshman and В. David Saunders, SICOMP 24 (1995), 387-397].

Асимптотически лучшие алгоритмы зачастую оказываются наихудшим решением для всех задач, к которым они применимы.

- Д. Д. КАНТОР (D. G. CANTOR) и Г. ЗАССЕНХАУЗ (Н. ZASSENHAUS) (1981)

УПРАЖНЕНИЯ

► 1. 1М24] Пусть р - простое число и пусть и{х)-случайный полином степени п. Считаем, что все р" нормированных полиномов равновероятны. Покажите, что, если п > 2, вероятность того, что и{х) имеет линейный множитель по модулю р, находится между (1--р~)/2 и (2--р")/3 включительно. Приведите точный вид этой вероятности при п > р. Чему равно среднее количество линейных множителей?

► 2. [MS5] (а) Покажите, что любой нормированный полином и{х) над областью единственного разложения может быть единственным образом представлен в виде

и{х) = v{x)w{x),

где w{x) свободен от квадратов (не имеет множителей положительной степени вида d{x)) и оба полинома-v{x) и w{x)-нормированы. (Ь) (Э. Р. Берлекамп (Е. R. Berlekamp).) Сколько нормированных полиномов степени п свободны от квадратов по модулю р, где р - простое число?

3. [М25] (Китайская теорема об остатках для полиномов.) Пусть и\{х), Ur{x) - полиномы над полем S, где щ{х) ± Uk{x) для всех j ф к. Докажите, что для любых данных полиномов uii(x), ..., Wr(x) над S имеется единственный полином v{x) над S, такой, что deg(t;) < deg(ui) + • • + deg(ur) и v{x) = Wj{x) moduj{x) для 1 < j < г. Справедливо ли это утверждение и в случае, когда S представляет собой множество всех целых чисел?

4. [НМ28] Пусть а„р - количество нормированных неприводимых полиномов степени п по модулю простого числа р. Найдите формулу для производящей функции Gp{z) = Ynp"- [Указание. Докажите следующее утверждение, касающееся степенных рядов: /() = Е>>1 9(2-) тогда и только тогда, когда g{z) = X;„>i p{n)f{z")/nK] Чему равен Ишр-юо апр/р?

5. [НМЗО] Пусть Апр-среднее количество неприводимых множителей выбранного случайным образом полинома степени п по модулю простого числа р. Покажите, что Ишр-юо Апр = Я„. Чему равно предельное среднее значение 2, где г - число неприводимых множителей?

6. [М21] (Ж. Л. Лагранж (J. L. Lagrange), 177L) Докажите тождество (9). [Указание. Разложите х - х в поле из р элементов.]

7. [М22] Докажите (14).

8. [НМ20] Как убедиться в том, что векторы, получаемые на выходе алгоритма N, линейно независимы?

9. [20] Объясните, каким наипростейшим образом можно построить таблицу обратных величин по модулю 101, если дано, что 2 является первообразным корнем числа 101.

► 10. [21] Найдите полное разложение по модулю 2 полинома и{х) из (22) с использованием процедуры Берлекампа.

11. [22] Найдите полное разложение полинома и{х) из (22) по модулю 5.

► 12. [М22] Используйте алгоритм Берлекампа для определения количества множителей и{х) = X* + 1 по модулю р для всех простых р. [Указание. Рассмотрите случаи, когда р = 2, р - 8к + 1, р = 8к + 3, р = 8к + 5, р = 8к + 7, отдельно. Чему при Этом равна матрица Q? Вам не нужно находить множители; требуется найти только их количество.]

13. [М25] Продолжая предыдущее упражнение, найдите точные формулы для множителей полинома х* -I- 1 по модулю р для всех нечетных простых чисел р с использованием величин л/-, V2, %/-2, если такие квадратные корни существуют по модулю р.

14. [М25] (Г. Зассенхауз (Н. Zassenhaus).) Пусть v{x) - решение (8) и пусть ии{х) = Yl{x - s), где произведение берется по всем О < s < р, таким, что gcd(u(x), v{x) - s) ф I. Объясните, как вычислить w(x) по данным и{х) и v{x). [Указание. Из формулы (14) вытекает, что w{x) является полиномом минимальной степени, таким, что и(х) делит w{v{x)).]

► 15. [М27] {Квадратные корни по модулю простого числа.) Разработайте алгоритм для вычисления квадратного корня целого числа и по модулю простого числа р, т. е. найдите число V, такое, что = и modp, если оно существует. Ваш алгоритм должен быть эффективен даже при очень больших целых числах р. (Для р ф 2 решение этой задачи сводится к ]1сшению квадратного уравнения по модулю р с использованием обычной квадратичной фо1)мулы.) Указание. Рассмотрите, что произойдет после применения методов разложения из этого раздела к полиному - и.

16. [МЗО] {Конечные поля.) Назначение данного упражнения-доказать основные свойства полей, введенных Э. Галуа (Е. Galois) в 1830 году, а) Дано, что f{x)-неприводимый по модулю простого числа р полином степени п. Докажите, что р" полиномов степени, меньшей п, образуют поле с арифметикой по

модулю f{x) и p. [Указание. Существование неприводимых полиномов любой степени доказано в упр. 4, поэтому поля с р" элементами существуют для всех простых чисел р и всех п > 1.]

b) Покажите, что любое поле с р" элементами имеет элемент "примитивный корень" f, такой, что элементами поля являются {О, f,. •. [Указание. В упр. 3.2.1.2-16 содержится доказательство для частного случая п = 1.]

c) Если f{x) - неприводимый полином по модулю р степени п, докажите, что хр" - х делится на f(x) тогда и только тогда, когда тп кратно п. (Отсюда следует, что можно быстро проверить неприводимость. Данный полином п-й степени f{x) неприводим по модулю р тогда и только тогда, когда хр" - х делится на f{x) и хр" - х 1. f{x) для всех простых q, которые делят п.)

17. [М23] Пусть F -поле с 13 элементами. Сколько эле.ментов F имеют порядок / для каждого целого 1 < / < 13? (Порядком элемента а является наименьщее положительное целое число т, такое, что a" = 1.)

► 18. [М25] Пусть и{х) = и„х"------huo, и„ ф О является примитивным полиномом с целыми

коэффициентами и пусть v{x) - нормированный полином, определяемый как

V{X) = • U{x/Un) =Х"+ U„-1X"~ -I- Un-2UnX"~ ++ ИОиГ-

(а) Дано, что v{x) имеет полное разложение pi(x).. .рг{х) над кольцом целых чисел, где каждый pj{x) нормирован. Каково полное разложение полинома и{х) над кольцом целых чисел? (Ь) Если w{x) = х"* -)- Wm-ix™~ + • + wo является множителем t(x), докажите, что Wk является множителем и~~* при О < к <тп.

19. [М20] (Критерий Эйзенштейна.) Возможно, самый известный класс неприводимых полиномов над кольцом целых чисел был введен Т. Шёнеманном (Т. Schonemann) в Crelle 32 (1846), 100, а популяризован Г. Эйзенштейном (G. Eisenstein) в Crelle 39 (1850),

166-169. Пусть р является простым числом и пусть полином и(х) = их" Н-----1- "о имеет

следующие свойства: (i) u„ не делится на р; (ii) u„ i, ..., uo делятся на р; (iii) uo не делится на р. Покажите, что и(х) неприводим над кольцом целых чисел.

20. [НМЗЗ] Если и{х) = Unx" -)-•+ uo является некоторым полино.мом над полем комплексных чисел, обозначим и = {\un\ Н-----)- иоН.

a) Пусть и(х) = (х - a)w{x) и v{x) = (ах - 1)и;(х), где а - произвольное комплексное число, а а - сопряженное ему. Докажите, что и = г;.

b) Пусть un(x - ai)... (х - а„) представляет собой полное разложение и(х) над полем комплексных чисел. Введем обозначение М{и) == un П"=1 ™а,х(1, aj ). Докажите, что М{и) < [\и\\.

c) Покажите, что \uj\ < ("j)M(u) + ("Zi)u„ для О < j < n.

d) Объедините эти результаты для доказательства того, что если и(х) = v{x)w{x) и

v{x) = VniX"" -\-----\-Vo, где и, V, W имеют целые коэффициенты, то коэффициенты г;

ограничены следующим образом:

к1<Г7)1Н1 + (7-/Ж1-

21. [НМ32] Продолжая упр. 20, выведем полезные границы коэффициентов полиномов от многих переменных над кольцом целых чисел. Для удобства будем использовать полужирные символы, чтобы обозначить последовательности из t целых чисел. Таким образом, вместо записи

u{xi,...,xt) = Uj,...j,x{...xi 31.....