AOP_Tom2 (1021737), страница 210
Текст из файла (страница 210)
Алгоритм Х может быть адаптирован для поиска коэффициентов ш. Пусть А— матрица размера (г+1) х и, в й-й строке которой содержатся коэффициенты о(х)" шос1 и(х) для 0 < й < г. Будем применять метод алгоритма Х до тек пор, пока не будет найдена первая зависимость на шаге ХЗ; затем алгоритм завершается с ш(х) = ос+о)х+ +оьх, э где оэ определены в (18). В этот момент 2 < 5 < г; заранее знать г не нужно, поскольку можно проверять зависимость после создания каждой строки А.
15. Можно считать, что и Р' 0 и что р нечетна. Из метода Берлекампа, примененного к папиному х — и, следует, что квадратный корень существует тогда н только тогда, э Эдесь Я вЂ” 1 имеет ранг 2, поэтому есть 4 — 2 = 2 множителя. [Однако легко доказать, что х + 1 неприводим над кольцом целых чисел, поскольку у него нет линейных множителей э и коэффициент при х в любом множителе степени 2 согласно упр. 20 должен быть не больше 2 по абсолютному значению (см. также упр. 32, поскольку х" + 1 = Фв(х)). Г.
П. Ф. Свнинертон-Дайер (Н. Р. Р. Зччппеггоп-Пуег) показал, что для всех 5 > 2 полиномы степени 2", непрнводимые над кольцом целых чисел, полностью разлшаются на линейные и квадратичные множители по модулю любого простого числа. Для степени 8 в качестве примера он привел полинам х — 1бхэ + 88хэ + 192х + 144, имеющий корни Ы/2 х т/3 хэ [см. Маей. Сошр. 24 (1970), 733-734). Согласно теореме Фро5ениуса (ггоЬеп1ея) из упр. 37 любой неприводимый полипом степени и, в группе Галуа которого не содержится п-циклов, будет иметь множители по модулю почти всех простых чисел.] 13.
Случай, когда р = 85 + 1: (х+ (1+~/-Т)/ъг2)(х + (1-~/-Т)/~/2)(х — (1+з/-Т)/с/2) к (х — (1- т/-Т)/ь/2). Случай, когда р = 85 + 3: (х~ + ч' — 2х — 1) (х~ — ~/-2х — 1). Случай, когда р = 85+ 5: (хе+ ~~~)(х~ — т/ — 1). Случай, когда р = 85+ 7: (к~+ чг2х+1) х (х — ч'2х + 1). Разложение для р = 85 + 7 также справедливо над полем действительных чисел. когда Я вЂ” 1 = О, либо тогда и только тогда, когда ит 'У~ тодр = 1, но зто нам уже известно.
Из метода Кантора н Зассенхауза в (20) или, что еще лучше, из (21) с д = 1 следует, что 8сд(х~ — и, (х+в)«в 'Н~ — 1) будет нетривиальным множителем с вероятностью > -,' при случайном выборе в. На практике выбор последовательных в работает так же, как и случайный выбор в, так что получается следующий алгоритм: "Вычислять 8сд(хв — и, х!в цгв — 1), бед(хв — и, (х+ 1)!в В/в — 1), 8сд(хв — и, (х+ 2)!в '!гз — 1), ... да тех пор, пока не будет найден первый наибольший общий делитель вида х + а.
Тогда ,/и = Ье'! Ожидаемое время работы алгоритма составляет 0(1обр) для больших р. Подробное рассмотрение показывает, что первый шаг этого алгоритма успешен тогда и талька тогда, когда ртод 4 = 3. Для р = 26+ 1, где 9 нечетно, имеем хв шод (х~ — и) = и!в В/ях и Зсд(гв — и,хв — 1) ш х — и!в+ Н, поскольку ия = 1 глод р.
В действительности формула «/й = хи!«+07~ п«од р, когда р шод 4 = 3, непосредственно дает квадратный корень. Однако, если ртод 4 = 1, получим х!в 'У~ шод (хв — и) = и!в ц!«и наибольший общий делитель будет равен 1. Поэтому приведенный выше алгоритм должен использоваться только при р шод 4 = 1 и первый наибольший общий делитель должен быть пропущен. Прямой метод, хорошо работающий при ршод8 = 5, был открыт в 90-х годах А. О.
Л. Аткином (А. О Ь. А1Ып) на основе того факта, что в этом случае 2!в — 1. Установить сначала с «- (2и)«в вцвшодр и «с- (2иев)тодр, затем — 1/й х(иа(« — 1)) тодр, а также «/-Т = шб (Сотригабола! Регяресбгея ол 7«итбег ТЬеогу (Са«нЪг!дбе, Мвявл 1лсегпайопа! Ргевя, 1998), 1 — 11; см. также Н. С. РосЫ!ой!оп, Ргоц СатЬ. РЫ!. Бос, 19 (1917), 57 — 59.) При ршад 8 = 1 необходимо прибегнуть к методу проб и ошибок.
В этом случае другие известные процедуры зачастую превосходит метод Дэниэла Шенкса (Ван!е! БЬапйв): предположим, чта р = 2'9 + 1. где е > 3. 81. Выбрать х случайным образом из диапазона 1 < х < р и установить в = хя шод р. Если яв' шодр = 1, повторить этот швг (среднее количество построений будет менее 2; на шагах Б2 и БЗ случайные числа не потребуются). На практике можно сэкономить время, перебирая малые нечетные простые числа х и останавливаясь с я = хв тод р, когда рш НГ« п«одх = х — 1; см. упр.
1.2.4-47. 82, Установить у+- в, г «- е, х г — и~в Нгв шод р, с «- их тодр, ю,'— ихз тодр. БЗ. Если ю = 1, остановиться; с прн этом содержит искомый ответ. В противном случае найти наименьшее Й, такое, что ив шад р равно 1.
Если Й = г, остановиться (ответ не существует); в противном случае установить (у.г,а,ю) « — (ув,й,аув « ~,юуэ «) н повторить шаг БЗ. ) Корректность этого алгоритма следует иэ тождеств-инвариантов июшсв ув" «ш — 1, юв" ' ш 1шадр. При ю ф 1 шаг БЗ выполняет г + 2 умножений по модулю р; следовательно, максимальное количество умножений ва этом шаге меньше, чем ( ), а «+3« среднее количество меньше -'('~ ). Таким образам, время работы составляет О(!ойр) для шагов Б1 и 82 плюс порядка е (1абр) для шага БЗ, по сравнению со временем 0(!ойр) для рандомизнраваннага метода, основанного на (21). Однако постоянный множитель в методе Шенкса мал. (Солбгеявив !«ишегалв!иш 7 (1972), 58-62.
Схохсий, но менее аффективный метод был опубликован в А. Топе!!1, СаЗх!лбег Хасбг!сбгеп (1891), 344 — 346. Первым алгоритм вычисления квадратного корня с ожидаемым временем работы 0(!ой р) открыл М. Чиполла (М. С«ра!!а), Яешбсопй Ассад. Боб Р!я. Мак «Уароб' 0 (1903), 154-163.) 16. (а) В доказательстве дяя п = 1 вместо целых чисел подставьте полииомы по модулю р. (Ъ) Доказательство для н = 1 распространяется на любое конечное пале. (с) Поскольку х = б для некоторого й, хг = х в поле, определенном /(х). К тому же множество ь элементов у, удовлетворяющих уравнению р» = у, в этом поле замкнуто по отношению к сложению и по отношению к умножению.
Так что если х» = х, то Е (будучи полиномом от х с целыми коэффициентами) удовлетворяет уравнению 6» = Е 17. Если б — примитивный корень, то каждый ненулевой элемент является некоторой степенью 6. Следовательно, порядок должен быть делителем 13 — 1 = 2 3 7 и порядок / имеют Ээ(/) элементов. / <о(/) 1 1 2 1 4 2 8 4 ФУ) 7 б 14 6 28 12 56 24 У к(/) 21 12 42 12 84 24 168 48 у Ф(/) 3 2 б 2 12 4 24 8 18. (а) Согласно лемме Гаусса рр(р<(и»х))...
рр(р„(и»х)). Например, пусть и(х) = бх — Зх + 2х — 1, о(х) = х — Зх + 12х — 36 = (х + 12)(х — 3); тогда рр(Збхз + 12) = Зхэ + 1, рр(бх — 3) = 2х — 1. (Это современная версия использовавшегося многие годы для решения алгебраических уравнений трюка 14 века.) (Ь) Пусть рр(ю(н»х)) = ю х + + юо = ю(и»х)/с, где с — содержание ю(и х) как полинома от х.
Тогда ю(х) = (сю/и» )х +- +сюе. Следовательно, сю = и»; поскольку ю,„ является делителем и», с кратное» 19. Если и(х) = о(х)ю(х) и при этом беб(с) беб(ю) > 1, то и х» ш с(х)ю(х) шопр. В соответствии с единственностью разложения по модулю р все коэффициенты с и ю, кроме старших, кратны р и р~ делит союо = нэ. 29. (а) 2 (пк. — и; <)(ои — н <) = 2 (и — би <)(й~ — ай <). (Ь) Можно считать, что ио ф О.
ПУсть т(и) = П», ш<п(1,]о ]) = [ио]/М(и). ПРи ]оэ] < 1 замените в и(х) множитель х — ог на бгх — 1. Это не повлииет на ЦиЦ, но заменит ]но[ на М(и). (с) иг = и х ач...а;,, представляя собой элементарную симметричную функцию. Следовательно, ]и~] < [им[2 <8<,... 8<,, где Д = шах(1, ]о,]). Завершим доказательство, показав, что при х< > 1, ..., х» > 1 и х<... х» = М элементарная симметричная функция и ь = х хн ... х;„< („",)М+("„) — предполагаемому значению при х, = = х», = 1 и х» = М.
(Если хч « х» < М, преобразование х» < — х <г, х» < +- 1 увеличивает а ь на о<» ю<» О(х» — 1)(х„< — 1), являющуюся положительной величиной.) (<1) [оу] < ( ')М(с) + (™ д'][си] < (и. ')М(и) + (™, )[и»], посколькУ М(о) < М(и) и ]о ] < ]и [. [М. М<бпосге, 1ИасЛ. Соп<р. 28 (1974), 1153 — 1157.] Прнмечаиия. Это решение показывает, что (и, ) М(и) + (~,')]и»] является верхней гранью, так что хотелось бы иметь лучшую оценку М(и). Известно несколько методов нахождения этих оценок [ЪЧ. БресЫ, МасЛ. Лей, 53 (1950), 357 — 363; Сегйепсо, М18поссе, аш1 Р<гаэ, Х Вуп<Ьо1<с Сошр.
4 (1987), 21 — 33]. Простейшим и наиболее быстро сходящимся, возможно, является следующий метод [см. С. Н. Стае<ус, Аибоэнпб дег Ьойегеп пшпепэсйеп Яшсйппбеп (Евг1сЬ, 1837)]. Полагая, что и(х) = и»(х — и<)... (х — о ), обозначим й(х) = и(~Гх)и(-,/х) = ( — 1)»иэ(х — а )... (х — а~). Тогда М(и) = М(й) < ЦйЦ. Следовательно, можно установить с < — ЦиЦ, о +- и/с, 1 < — О, а затем несколько раз установить 1 + — 1+ 1„с < — ЦОЦ'<~ с, о +- О/ЦОЦ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
