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