случайного t{x) степени < rd вместо того, чтобы ограничиться выбором полинома степени <2d.

30. Пусть Т{х) = х + х -{-----\-хР - след х и пусть v{x) = T{t{x)) mod q{x). Поскольку

t{x)p = t{x) в поле полиномиальных остатков по модулю q{x), имеем в этом поле t;(x) = v{x); другими словами, t;(x) является одним из р корней уравнения уР - у = 0. Значит, v{x)-целое число.

Отсюда следует, что ПГ=о ecd{gd{x),T{t{x)) - s) = gd(x). В частности, когда р = 2, можно, как в упр. 29, утверждать, что gcd(gd(x), T(t(x))) будет собственным делителем gd{x) с вероятностью > j, если gd(x) имеет хотя бы два неприводимых множителя и t{x) - случайный бинарный полином степени < 2d.

[Заметьте, что T(t(x)) modg(x) может быть вычислено, начиная с и(х) <- t{x), и после установки d - 1 раз и(х) <- {t{x) + u(x)) modg(x). Метод этого упражнения основан на разложении полиномов хр"* - х = ПГ=о (-С) ~ *)> которое справедливо для любого р, в то время как формула (21) основана на разложении хр"* - х = x(x(p-U/2 + 1)(x(p-i)/2 - 1) для нечетных р.]

"След" был введен Ричардом Дедекиндом (Richard Dedekind), Abhandlungen der Konigl. Gesellschaft der Wissenschaften zu Gottingen 29 (1882), 1-56. Использование метода вычисления gcd(/(x), Г(х) -s) для поиска множителей /(х) было прослежено до А. Эрвина (А. Arwin), Arkiv for Mat., Astr. och Fys. 14,7 (1918), 1-46; однако его метод был не полон, потому что он не рассматривал T(t(x)) для t{x) ф х. Алгоритм полного разложения с использованием следов был разработан позже Р. Д. Мак-Элисом (R. J. МсЕНесе), Math. Сотр. 23 (1969), 861-867; см. также von zur Gathen and Shoup, Computational Complexity 2 (1992), 187-224, алгоритм 3.6 (дающий асимптотически быстрые результаты).

Генри Кохен (Henri Cohen) обнаружил, что при использовании этого метода дляр = 2 достаточно проверить не более d специальных случаев t(x) = х, х, ..., х~. Один из этих выборов t(x) гарантированно разбивает gd{x) на множители, если gd приводим, потому что можно получить результаты всех полиномов t(x) степени < 2d из этих частных случаев, если использовать тот факт, что Г(*(х)) = Г(*(х)) и Т(и(х) + t(x)) = Г(и(х)) + T(t(x)) (по модулю gd(x)). [А Course in Computational Algebraic Number Theory (Springer, 1993), Algorithm 3.4.8.]

31. Если a -элемент поля из p"* элементов, обозначим через d{a) степень а, а именно - наименьший показатель степени е, такой, что аР = а. Затем рассмотрим полином

Ра(х) = (х - а){х - а")... (х - ар-) = да{х)"\

где да{х) - неприводимый полином степени d{a). При а, пробегающем по всем элементам этого поля, соответствующий полином да (х) пробегает по всем неприводимым полиномам степени е, делящим d, где каждая такая "неприводимость" встречается в точности е раз. Имеем (х + t)p~У mod да{х) = 1 тогда и только тогда, когда в поле (а + t " = 1. Если t - целое число, имеем d{a + t) = d(a); следовательно, п(р, d) в d~ раз превышает число элементов а степени d, таких, что a(p-i)/2 = 1. Аналогично, если ti ф ta, нужно выяснить количество элементов степени d, таких, что (a + ti)(p-)/2 = {a + t2yp~или, что то же самое, {{а + ti)/(a + t2))p~>/ = 1. При а, пробегающем по всем элементам степени d, справедливо равенство {а + ti)/(a + ta) = 1 + (ti - *2)/(а + ta).

[Имеем n(p,d) = jd" I2c\rf( + {-lV)p{c)(p ~ 1), что составляет около половины общего числа "неприводимостей" (в точности половину при нечетном d). Это доказывает, что gcd(gd(x), (х + t)(p-)/2 1) дает хорошие шансы найти множители gd(x) при фиксированном t и случайным образом выбранном gd(x); однако рандомизированный алгоритм предлагается для работы с гарантированной вероятностью для фиксированного gd{x) и случайного t, как в упр. 29.]

32. (а) Ясно, что х"-1 = Yla\n<i() поскольку каждый комплексный п-й корень единицы является примитивным d-м корнем некоторого уникального d\n. Второе тождество следует из первого; Фп(х) имеет целые коэффициенты, поскольку они выражаются через члены произведений и частных нормированных полиномов с целыми коэффициентами.

(b) Условия, приведенного в указании, достаточно для доказательства того, что f{x) = Фп(х). Когда р не делит п, имеем ж" - 1 ± пж""" по модулю р, следовательно, полином ж" - 1 свободен от квадратов по модулю р. При данных /(ж) и (, таких, как описано в указании, обозначим через д{х) неприводимый множитель Фп(ж), такой, что giC) = 0. Если д{х) ф /(ж), то /(ж) и д(ж) - различные множители Фп(ж). Значит, они являются различными множителями ж" - 1 и, следовательно, не имеют неприводимых множите.лей по общему модулю р. Однако является корнем д(ж), так что gcd(/(ж),g(ж)) ф 1 над кольцом целых чисел, и поэтому /(ж) является делителем д(ж). Согласно (5) /(ж) - делитель (ж) по модулю р, а это противоречит предположению, что /(ж) и д(ж) не имеют общих неприводимых множителей. Поэтому /(ж) = (ж). [Неприводимость Фп(ж) впервые была доказана для простых чисел п Гауссом в Disquisitiones Aritlimeticae (Leipzig, 1801), Art. 341, и Кронекером для произвольных п в J. de Matii. Pures et Appliquees 19 (1854), 177-192.]

(c) Ф1(ж) = ж - 1, и при простом р Фр(ж) = 1 + X + + ж". Если п > 1 нечетно, нетрудно доказать, что Ф2п(ж) = Фп(-ж). Если р делит п, второе тождество в п. (а) показывает, что Фрп(ж) = Я>„(х). Еслир не делит п, то имеем Фр„(ж) = Фп(ж)/Фп(ж). Для составного же п < 15 имеем Ф4(ж) = х + 1, Фв(ж) = х - х + 1, Ф8(ж) = х* + I, %{x) = жЧжЧ1, Ф1о(ж) = ж-жЧж-ж-М, Ф12(ж) = х*-хЧ1, Ф14(ж) = ж«-жЧж"-жЧж-ж- 1, Ф15(ж) = ж*-жЧж-жЧжЗ-ж--1. [Формулу Фр,(ж) = (1-ЬжР-Ь-.---ж(«-"Р)(ж-1)/(ж«-1) можно использовать для того, чтобы показать, что все коэффициенты Фр,(ж) равны ±1 или О при простых р и q\ однако коэффициенты Фр,г(ж) могут быть произвольно велики.]

33. Ложно; мы теряем все pj с ej, делимыми на р. Истинно, если р > deg(M) [см. упр. 36.]

34. [D. Y. У. Yun, Ргос. АСМ Symp. Symbolic and Algebraic Сотр. (1976), 26-35.] Установить {t{x),vi{x),wi{x)) <- ССВ(м(ж),м(ж)). Если ((ж) = 1, установить е 1; в противном случае устанавливать {ui{x),Vi+i{x),Wi+i(x)) <- GCD(t)i(x),ui(ж) - Vi(x)) для i = 1, 2,..., е - 1 до тех пор, пока не будет найдено We (ж) - v (ж) = 0. И наконец установить

ие(ж) Ve{x).

Для доказательства корректности этого алгоритма заметим, что он вычисляет полиномы t{x) = М2(ж)мз(ж)М4(а;) ...,Vi(x) = Mi(ж)Mi+l(ж)Mi+2(ж). .. и

ил(ж) = М(ж)м;+1(ж)м;+2(ж) . . .--2Mi(ж)мi+(ж)Ui+2(ж) . . . + 3Ui{x)Ui+l{x)Ui+2{x) • + • • •

Имеем t{x) J wi{x), поскольку неприводимый множитель Mi(ж) делит все, кроме г-го, члены w\{x) и является взаимно простым по отношению к этому члену. Ясно и то, что

Mi(ж) 1 Vi+l{x).

[Хотя в упр. 2, (Ь) доказывается, что большинство полиномов свободно от квадратов, на практике часто встречаются полиномы "с квадратами"; следовательно, этот метод становится весьма важным. Предложения по его усовершенствованию приводятся в Paul S. Wang and Barry М. Trager, SICOMP 8 (1979), 300-305. Разложение по модулю р, свободное от квадратов, рассматривается также в Bach and Shallit, A/g-oritiimic Number Theory 1 (MIT Press, 1996), ответ к упр. 7.27.]

35. Имеем гиДж) = gcd(uj(ж),г)•(ж)) gcd{uj+i{x),Vj{x)), где

uj (ж) = Uj {X)UJ+1 (ж) . . . и V] (ж) = Vj (ж) Vj + l{x)... .

[Юнь отмечает, что время работы свободного от квадратов разложения по методу упр. 34 не более чем в два раза превышает время вычисления gcd(м(ж),м(ж)). Кроме того, если

дан произвольный метод свободного от квадратов разложения, метод из этого упражнения приводит к процедуре поиска наибольшего общего делителя. (В случае, когда и{х) и v{x) свободны от квадратов, их наибольший общий делитель просто равен гиг (ж), где w{x) = u{x)v{x) = wi{x)w2{x); все полиномы Uj{x), Vj{x), Uj{x) и v]{x) свободны от квадратов.) Следовательно, задача преобразования примитивного полинома степени п в его свободное от квадратов представление с точки зрения вычислений эквивалентна задаче поиска наибольшего общего делителя двух полиномов степени п в смысле асимптотического времени работы для наихудшего случая.]

36. Пусть Uj{x)-значение, вычисленное для "щ{хУ по процедуре из упр. 34. Если

deg(C/i) + 2deg(C/2)H----= deg(M), то щ{х) = Uj{x) для всех j. Однако в общем случае у нас

будет е <pkUj (ж) = П>о %+р*() Д- 1 < j < Р- Для дальнейшего разделения этих множителей можно вычислить t{x)l{U2{x)U3{xY . .Up-i{xY~) = \[]>рч{У = z{x). После рекурсивного поиска свободного от квадратов представления z{x) = {zi (ж), Z2{x),...) получим zk{x) = no<j<p %+рь() так что можно вычислить отдельные щ(,х) по формуле gcd{Uj{x),Zk{x)) = Mj+pfc(x) для 1 < i < р. Полином Upk{x) останется, в то время как другие множители Zk{x) будут удалены.

Примечание. Эта процедура очень проста, но реализующая ее программа длинна. Если необходима короткая, а не предельно эффективная программа для полного разложения полиномов по модулю р, то, вероятно, проще будет модифицировать программу разложения с различными степенями так, чтобы она давала gcd(xp - ж,м(ж)) несколько раз для одного и того же значения d до тех пор, пока наибольший общий делитель не станет равным 1. В этом случае нет необходимости начинать с вычисления gcd(M(x), м(ж)) и удаления кратных множителей, как было предложено в тексте разде.та, поскольку полином жР - ж свободен от квадратов.

37. Точное значение вероятности составляет Y{j>l{ipP)li-i где kj-количество dj, равных j. Поскольку согласно упр. 4 ajp/p « получим формулу из упр. 1.3.3-21.

Примечания. Из этого упражнения следует, что если зафиксировать простое число р и случайным образом выбрать полином м(ж), то возникнет определенная вероятность его разложения указанным путем по модулю р. Более сложная задача состоит в определении вероятности при фиксированном полиноме м(ж) и "случайном" простом числе р, которое приводит к одному и тому же асимптотическому результату для почти всех м(ж). Г. Фробениус (G. Probenius) доказал в 1880 году (хотя результат не был опубликован до 1896 года), что целый полином и{х) разбивается по модулю р на множители степени di,..., dr при случайным образом выбранном большом простом р с вероятностью, равной числу перестановок в группе Галуа G из полиномов м(ж), которые имеют длины циклов {di,...,dr}, деленной на общее количество перестановок в G. [Если м(ж) имеет рациональные коэффициенты и различные корни • • • i ?п над полем комплексных чисел, его группа Галуа представляет собой единственную группу G перестановок, такую, что псшином Пр(1)...р(п)ео(г + ?р(1)У1 + • • • + (.р(п)Уп) = U{z,yi,... ,у„) имеет рациональные коэффициенты и неприводим над полем рациональных чисел; см. G. Probenius, Sitzungs-beridite Konigl. preuB. Akad. Wiss. (Berlin, 1896), 689-703. Линейное отображение ж ж традиционно называется автоморфизмом Фробениуса, как в его знаменитой статье.] Кроме того, Б. Л. ван дер Варден (В. L. van der Waerden) доказал в 1934 году, что почти все полиномы степени п имеют множество всех п! перестановок в качестве их группы Галуа [Math. Annalen 109 (1934), 13-16]. Поэтому почти все фиксированные неприводимые полиномы м(ж) будут множителями, как можно ожидать, по отношению к случайному выбору большого простого числа р. [См. также работу N. Chebotarev, Math. Annalen 95 (1926), в которой представлено обобщение теоремы Фробениуса для сопряженных классов трупп Галуа.]