когда Q - I = О, либо тогда и только тогда, когда и- modp = 1, но это нам уже известно. Из метода Кантора и Зассенхауза в (20) или, что еще лучше, из (21) с d = 1 следует, что gcd{x-u, (x + sY~ - l) будет нетривиальным множителем с вероятностью > 5 при случайном выборе е. На практике выбор последовательных s работает так же, как и случайный выбор я, так что получается следующий алгоритм: "Вычислять gcd(x2 - и, х"- - 1), gcd(x2 - U, (х + 1)(Р-1)/2 - 1), gcd(x2 - U, (х + 2)(Р-/2 - 1), ... до тех пор, пока не будет найден первый наибольший общий делитель вида х + v. Тогда у/й = ±v". Ожидаемое время работы алгоритма составляет O(logp) для больших р.

Подробное рассмотрение показывает, что первый шаг этого алгоритма успешен тогда и только тогда, когда р mod 4 = 3. Для р = 2д + 1, где q нечетно, имеем х mod (х - и) = ц(«-1)/2д. JJ gcd(x2 - U, х - 1) = X - ««+2 поскольку и = 1 mod р. В действительности формула у/й = iumodp, когдар mod 4 = 3, непосредственно дает квадратный корень.

Однако, если р mod 4 = 1, получим х- mod (х - и) = u~>* и наибольший общий делитель будет равен 1. Поэтому приведенный выше алгоритм должен использоваться только при р mod 4 = 1 и первый наибольший общий делитель должен быть пропущен.

Прямой метод, хорошо работающий при pmodS = 5, был открыт в 90-х годах А. О. Л. Аткином (А. О. L. Atkin) на основе того факта, что в этом случае г- = -1. Установить сначала v (2u)modp и t <- {2uv)modp, затем-у/й = ±(иг;(г - 1)) modp, а также = ±t. [Computationa/ Perspectives on Number Theory

(Cambridge, Mass.: International Press, 1998), 1-11; см. также Н. С. Pocklington, Proc. СашЬ. Phil. Soc. 19 (1917), 57-59.]

При p mod 8 = 1 необходимо прибегнуть к методу проб и ошибок. В этом случае другие известные процедуры зачастую превосходит метод Дэниэла Шенкса (Daniel Shanks): предположим, что р = 2д -I-1, где е > 3.

51. Выбрать X случайным образом из диапазона 1 < х < р и установить г = х modp. Если z~ modp = 1, повторить этот шаг (среднее количество построений будет менее 2; на шагах S2 и S3 случайные числа не потребуются). На практике можно сэкономить время, перебирая малые нечетные простые числа х и останавливаясь с 2 = х modp, когда р") modx = х - 1; см. упр. 1.2.4-47.

52. Установить г/ +- 2, г е, х и- modp, v их modp, w <- ux modp.

53. Если u; = 1, остановиться; v при этом содержит искомый ответ. В противном случае найти наименьшее А;, такое, что ui* modp равно 1. Если к = г, остановиться (ответ не существует); в противном случае установить

{y,r,v,w) {y~,k,vy"~"\wy")

и повторить шаг S3.

Корректность этого алгоритма следует из тождеств-инвариантов uw = v, 3/-= -1, w" = 1 modp. При w ф 1 шаг S3 выполняет г + 2 умножений по модулю р; следовательно, максимальное количество умножений на этом шаге меньше, чем (*), а среднее количество меньше Kt)- Таким образом, время работы составляет O(logp)* для шагов S1 и S2 плюс порядка е (logp) для шага S3, по сравнению со временем O(logp) для рандомизированного метода, основанного на (21). Однако постоянный множитель в методе Шенкса мал. [Congressus iVumerantium 7 (1972), 58-62. Схожий, но менее эффективный метод был опубликован в А. Tonelli, Gottinger Nachrichten (1891), 344-346. Первым алгоритм вычисления квадратного корня с ожидаемым временем работы O(logp) открыл М. Чиполла (М. CipoUa), Rendiconti Accad. Sci. Fis. Mat. Napoli 9 (1903), 154-163.]

16. (a) В доказательстве для n = 1 вместо целых чисел подставьте полиномы по модулю р. (Ь) Доказательство для п = 1 распространяется на любое конечное поле, (с) Поскольку

X = для некоторого А;, хр" = х в поле, определенном /(х). К тому же множество элементов у, удовлетворяющих уравнению j/p" = j/, в этом поле замкнуто по отношению к сложению и по отношению к умножению. Так что если хр" = х, то (будучи полиномом от x с целыми коэффициентами) удовлетворяет уравнению р" = .

17. Если - примитивный корень, то каждый ненулевой элемент является некоторой степенью . Следовательно, порядок должен быть делителем 13 - 1 = 2 • 3 • 7 и порядок / имеют (p(f) элементов.

18. (a) Согласно лемме Гаусса pp(pi(unx)).. .pp(pr(unx)). Например, пусть

u(x) = 6х - Зх + 2х - 1, г;(х) = х - Зх + 12х - 36 = (х + 12)(х - 3);

тогда рр(36х + 12) = Зх + 1, рр(6х - 3) = 2х - 1. (Это современная версия использовавшегося многие годы для решения алгебраических уравнений трюка 14 века.)

(Ь) Пусть pp(u;(u„x)) = Wmx" Н-----h iDo = iu(u„x)/c, где с - содержание w{unx) как

полинома от х. Тогда w{x) = {cw/u)x" Н-----hcwo- Следовательно, cwm = «?Г; поскольку

Wm является делителем Un, с кратно и".

19. Если и{х) = t;(x)u;(x) и при этом deg(i;) deg(u;) > 1, то Unx" = i;(x)u;(x) modp. В соответствии с единственностью разложения по модулю р все коэффициенты v и w, кроме старших, кратны р и р делит vowo = uq.

20. (а) J(auj - Uj-i){auj - uj-i) = E("j ~ uuj i)(uj - auj-i). (b) Можно считать, что Uo Ф 0. Пусть т{и) = Г1"=1 «im(l, aj) = uo/M(u). При < 1 замените в u(x) множитель х - aj на ajx - 1. Это не повлияет на и, но заменит uo на М(и).

(c) Uj = Um Е**! • • •*m-ji представляя собой элементарную симметричную функцию. Следовательно, uj < um Е • • • Am -j > W А = max(l, \ai\). Завершим доказательство, показав, что при xi > 1, ..., Хп > 1 и xi ... Хп = М элементарная симметричная функция "nfc = ЕXii •.. Xi < i1Zl)M+i"k) -предполагаемому значению при xi = • • • = Xn-i = 1 и Xn = М. (Если Xl < ••• < Хп < М, преобразование Хп Xn-iXn, Xn-i 1 увеличивает ак на (7(„ 2)(fc i)(xn - l)(xn-i - 1), являющуюся положительной величиной.)

(d) \vj\ < {"-)M(v) + (7 -i)bm < ("7)M(u) + (7 -;)u„, поскольку M(v) < M(u) и \vm\ < u„. [M. Mignotte, Math. Сотр. 28 (1974), 1153-1157.]

Примечания. Это решение доказывает, что ("~)М(и) + {jZi)\un\ является верхней гранью, так что хотелось бы иметь лучшую оценку М(и). Известно несколько методов нахождения этих оценок [W. Specht, Math. Zeit. 53 (1950), 357-363; Cerbenco, Mignotte, and Pitas, J. SymboUc Сотр. 4 (1987), 21-33]. Простейшим и наиболее быстро сходящимся, возможно, является следующий метод [см. С. Н. GraefFe, AuHosung der hoheren numerischen Gleichungen (Ziirich, 1837)]. Полагая, что u(x) = Un{x - ai)... (x - an), обозначим u(x) = и()и(-лД) = i-l)ul{x-aЬ..{x-al). Тогда M(u)= = М(й) < \\й\\. Следовательно, можно установить с и, v u/c, t О, а затем несколько раз установить t t + 1, с +- г)р/ с, г; г)/г). Инвариантные соотношения М{и) = cM{v)/ и г; = 1 гарантируют, что М(и) < с на каждом шаге итерации. Заметьте, что, когда г;(х) = г;о(х) + xi;i(x), мы имеем v(x) = vo(x) - xvi{x). Можно показать, что если каждое < р или > 1/р, то М(и) = u(l + 0(р)); следовательно, с после t шагов будет равно М(и)(1+0(р2)).

Налример, если и(х) представляет собой полином из (22), последовательные значения с для t = О, 1, 2, ... оказываются равными 10.63, 12.42, 6.85, 6.64, 6.65, 6.6228, 6.62246, 6.62246, .... В этом примере р » .90982. Заметьте, что сходимость не монотонна. В конечном итоге v{x) сходится к одночлену х"", где пг - количество корней с < 1, в предположении, что \aj\ ф 1 для всех j\ в общем, если имеется к корней с \olj\ = 1, коэффициенты при х"" и х"""*"* не достигнут нуля, в то время как это произойдет с коэффициентами при высших и низших степенях х.

Известная формула Дженсена [Acta Math. 22 (1899), 359-364] доказывает, что М(и) является геометрическим средним и(х)[ в единичном круге, а именно -

exp(/„2ln/(e)d).

В упр. 21, (а) будет аналогично показано, что {и является средним квадратичным и(х) в единичном круге. Неравенство М(и) < и, восходящее к Э. Ландау (Е. Landau) [Bud. Soc. Math, de ¥та.псе 33 (1905), 251-261], может поэтому трактоваться как соотношение междз средними значениями. Число М(и) часто называется мерой Махлера полинома, потому что Курт Махлер (Kurt Mahler) использовал его в Mathematiia 7 (1960), 98-100. Дженсен также доказал, что J" е""" 1п/(е) dd = - EJi aT/{2mmax{\aj\, l)") при ш > 0.

21. (а) Коэффициент при apbqCrd, равен нулю с обеих сторон, кроме случая p + s - q + r. Когда это условие выполняется, коэффициент справа равен (p + s)!; слева он составляет

[В. Beauzamy and J. Degot, IVans. Amer. Math. Soc. 345 (1995), 2607-2619; D. Zeilberger, AMM 101 (1994), 894-896.]

(b) Пусть Op = t;p, 6q = Wq, Cr = tr, d, = w,. Тогда правая сторона (a) равна В{и), а левая сторона представляет собой сумму неотрицательных членов для каждого j и к. Если рассмотреть только члены, где Sj является степенью v, члены t;p/(p - j)! исчезнут, за исключением р = j. Эти члены сводятся к

[В. Beauzamy, Е. Bombieri, P. Enflo, and H. Montgomery, J. Number Theory 36 (1990), 219-245.]

(c) Добавление новой переменной при необходимости достичь однородности не меняет соотношения и = vw. Таким образом, если v и w имеют общие степени тип соответственно, получаем (т + п)! [и] > т\ [v п\ [w]; другими словами, [v][w] < ("")[и].

Существует один изящный способ рассмотрения нормы Бомбьери, заключающийся в том, чтобы представить, что переменные некоммутативны. Например, вместо Зху - zw можно записать xyyy+jyxyy+jyyxy+yyyx-zzww-zwzw-zwwz-wzzw~wzwz~ wwzz. Тогда норма Бомбьери будет представлять собой норму новых коэффициентов. Другой интересной формулой для однородного полинома и степени п является

[uf = - [ /е-?---"--" u(x + iy)2dxdy. п. тг Jy

(d) Случай с одной переменной соответствует t = 2. Предположим, что и = vw, где v - однородный полином степени m от f переменных. Тогда г;крк!/т! < [t;] для всех к и к! > (m/t)!, поскольку logr(x) выпукла при х > 0; поэтому \vk\ < т\ [v]/(m/ty.*. Можно положить, что т! [t;]7(n/t)! < т\[w]/{m/ty.\ где т = п - т - степень w. Тогда

jtkj < т\ [v]/{m/ty.* < т\т\ [v][w]/{m/ty.(m/ty. < nl" [u]/(n/2t)!.