Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 29
Текст из файла (страница 29)
упр. 22). Если применить лемму Хенселя к (23) с р = 13 и е = 2, получится единственное разложение и(х) ы (х — 36)(хэ — 18х~ + 82х — 66)(хв + 34х — 10х~ + 69х+ 84) (по модулю 169). Обозначив эти множители как ~ (х)еэ(х)щ(х), мы видим, что ни в~(х) и еэ(х) не являются множителями и(х) над кольцом целых чисел, ни их произведение е~(х)цэ(х) с приведенными по модулю 169 к диапазону ( — +, з ) коэффициентами. Итак, мы использовали все возможности доказательства того, что и(х) неприводим над кольцом целых чисел — на этот раз используя только его разложение по модулю 13. Рассмотренный выше пример нетипичен в одном важном отношении: выполнялось разложение нормированного полинома и(х) из (22), поэтому можно считать, что все его множители нормированы.
Что же делать в случае, когда и„> 17 В такой ситуации старший коэффициент одного из множителей полннома может почти произвольно варьироваться по модулю р', мы, конечно, не хотим рассматривать все имеющиеся возможности. Вероятно, читатель уже заметил эту проблему. К счастью, существует простой выход: разложение п(х) = е(х) ю(х) влечет за собой разложение нън(х) = е~(х)ю~(х), где К(е~) = 1(нь) = н„= 4(н). (" Простите, вы не забыли, что я умножил ваш полипом на старший коэффициент перед разложением7") Теперь можно действовать так же„как и выше, с использованием р" > 2В, где В ограничивает максимальный коэффициент множителя и„и(х), а не и(х). Другой путь решения проблемы старшего коэффициента обсуждается в упр.
40. Объединим весь рассмотренный материал в следующей процедуре. Р1. Найти единственное свободное от квадратов разложение н(х) г— в с(и)п~(х)...е„(х) (по модулю р'), где р' достаточно велико, как пояснялось выше, и где еу(х) — нормированный полином. (Это будет возможно для некоторых простых чисел р: см. упр. 23.) Установить также 8 < — 1. Г2. Для каждой комбинации множителей п(х) = ец(х)...е;,(х) с э~ = 1, если и = -,'г, построить уникальный полипом 6(х) = 4(н)е(х) (по модулю р'), коэффициенты которого находятся в интервале ( — -'р' .. —,'р').
Если б(х) делит 8(и)и(х), вывести множитель рр(й(х)), разделить на него и(х), удалить соот- ветствующий и,(х) из списка множителей ло модулю р', уменьшить г на число удаленных множителей и завершить работу алгоритма, если И > Зг. РЗ. Увеличить Н на 1 и вернуться к шагу Р2, если Ы < -'г. 1 В заключение этого процесса текущее значение и(х) будет последним неприводимым множителем изначально заданного полинома. Заметьте, что, если ]ио] < ]и ], предпочтительно выполнять всю работу с "обращенным полиномом" иех" + " .
+ и„, множители которого представляют собой "обращенные" множители и(х). Описанная процедура требует выполнения условия р' > 2В, где  — граница коэффициентов любого делителя и„и(х), но можно использовать и гораздо меньшее значение В, если гарантировать, что оно будет верно для делителей степени < -'бей(и). В этом случае тест иа делимость на шаге Р2 должен применяться к ю(х) = и1(х)... и„(х)/и(х), а не к и(х) всякий раз, когда де8(и) > -' йе8(и), Можно еще больше снизить В, если гарантировать, что В ограничивает коэффициенты по меньшей мере одного корректного делителя и(х) (например, при разложении составного целого Х вместо лолинома некоторые делители могут быть очень большими, но хотя бы один из них будет < ~/Ю). Эта идея, предложенная и работе В, Веацхагпу, У, Тгег1зап, Р.
Б, ~%ап8, Х ЗутбоЛс Сошр. 16 (1993), 393-413, обсуждается в упр. 21. Проверка делимости на шаге Г2 должна в таком случае быть применена и к в(х), н к ю(х), но вычисления при этом будут выполняться быстрее, так как р' будет иметь гораздо меньшее значение. Описанный выше алгоритм имеет очевидное слабое место: может возникнуть необходимость в проверке для 2' ' — 1 потенциальных множителей и(х), Среыи нее значение 2' в случайной ситуации составляет порядка л или, возможно, л'г (см. упр. 5), но в противном случае понадобится ускорить данную часть программы настолько, насколько это окажется возможно.
Один из способов быстрого исключения ложных множителей состоит в первоначальном вычислении младшего коэффициента 6(0) с продолжением, только если он делит Е(и)и(0). Сложности, рассмотренные в предыдущих абзацах, не возникают, если это условие делимости не выполнено, поскольку такая проверка корректна даже при с)е8(и) > пей(и). Другой важный способ ускорения процедуры состоит в таком уменьшении г, чтобы оно отражало истинное количество множителей. Алгоритм разложения на различные Степени, приведенный выше, приложим к различным малым простым числам р„, Таким образом, для каждого простого числа получается множество Юы возможных степеней множителей по модулю ры (см. упр. 26). Можно представить Ю.
в виде строки из п битов. Теперь вычислим пересечение П Ю., т. е. побитовое аЮ этих строк, и выполним шаг Г2 только для бе8(11)+ "+бей(1ы) Е ГЧР1. Кроме того, р выбирается таким образом, чтобы ры имело наименьшее значение г. Эта технология разработана Дэвидом Р. Мюссером (РагЫ К. Мигвег), который, исходя из своего опыта, предложил испытывать около пяти простых чисел ры [см. 2АСМ 26 (1978), 271-282]. Конечно, следует немедленно остановиться, если текущее пересечение () Ю показывает, что полипом и(х) является неприводимым. Мюссер привел полное обсуждение метода разложения, подобного описанному выше, в 2АСМ 22 (1976), 291-308. Шаги Г1-ГЗ объединяются в усовершенствованном варианте, предложенном в 1978 году Дж.
Э. Коллинзом (О. Е, Со111пе). Он заключается в поиске пробных делителей путем одновременного получения комбинаций из 4 множителей вместо комбинаций с общей степенью 4. Это усовершенствование важно в связи со статистическим поведением множителей полиномов по модулю р, которые неприводимы над полем рациональных чисел (см.
упр, 37). А. К. Ленстра (А. К. Еепэсга), Х. В. Леистра (мл.) (Н. Ж. 1епэсга, Яг.) и Л. Ловас (1.. 1.огйвв) предложили свой известный "1.1Л.-алгоритм" разложения лолинома над кольцом целых чисел с точными границами количества вычислений в худшем случае (Магй, Аппа!еп 261 (1982), 515-534]. Их метод пе требует случайных чисел, а время его работы для полииома и(х) степени и составляет 0(пьт + п~((об()и(() ) битовых операций, где ((и(( определяется в улр.
26. Эта оцеика включает время поиска подходящего простого числа р и всех множителей ло модулю р при помощи алгоритма В. Конечио, эвристические методы, использующие рандомизацию, на практике работают значительно быстрее. Наибольшие общие делители. Подобные технологии могут применяться и для вычисления наибольших общих делителей полиномов: если бей(и(х),и(х)) = И(х) над кольцом целых чисел и если йсс1(и(х), и(х)) = 4(х) (по модулю р), где 4(х)— нормированный поливом, то ~((х) является общим делителем и(х) и и(х) по модулю р; следовательно, 6(х) = с йсо(и(х),и(х)), где константа с выбирается таким образом, что с(й) = Ксо(г(и), г(ю)) ° (26) Выбрав подходящее с, можно всегда достичь выполнения данного условия, поскольку старший коэффициент любого общего делителя и(х) и и(х) должен быть делителем йсо(г(и),с(и)).
Как только будет найден Й(х), удовлетворяющий этим условиям, можво будет легко вычислить рр(4(х)), который и является истинным наиболыпим общим делителем и(х) и и(х). Условие (26) удобно тем, что позволяет И(х) делит 4(х) (по модулю р). (24) Если р не делит старшие коэффициенты ии и, ни и, то р яе делит и старший коэффициент И; в таком случае Йеб(Н) < Йеб(д). Если для такого простого р д(х) = 1, то оеб(И) = О и п(х) = бед(сопг(и),сопг(о)). Это подтверждает сделанное в разделе 4.6.1 примечание о том, что простого вычисления бес((и(х), и(х)) по модулю 13 в 4.6.1-(6) достаточио для доказательства того, что и(х) и е(х) взаимно просты над кольцом целых чисел; тем самым сравнительно трудцемких вычислений согласно алгоритму 4.6.1Е или 4.6.1С можио избежать.
Поскольку два случайньгх примитивных лолинома почти всегда взаимно просты над кольцом целых чисел и поскольку они взаимно просты по модулю простого числа р с вероятностью 1 — 1/р в соответствии с упр. 4.6.1-5, вычисления обычно стоит производить по модулю р. Как отмечалось ранее, нужны хорошие методы и для неслучайных лолиномов, встречающихся на практике. Таким образом, мы хотим улучшить свои методы и научиться находить бсо(и(х),и(х)) в общем случае иад кольцом целых чисел, основываясь только иа информации, которая была получена при работе по модулю простых чисел р.
Можно считать, что и(х) и и(х) — примитивные полииомы. Вместо непосредственного вычисления боб(и(х), и(х)) удобнее искать лилином избежать неопределенности кратности наибольшего общего делителя обратимым элементам; использовалась, по существу, та же идея для контроля над старшими коэффициентами в программе разложения на множители. Если р — достаточно большое простое число, которое основано на границах коэффициентов из упр. 20, приложенных к сф)н(х) либо к 4(8)е(к), вычислим единственный полипом 4(х) гв 4(Ы)д(х) (по модулю р), все коэффициенты которого находятся в диапазоне [ — зр.. -'Р).
Если рр(д(х)) делит как и(х), так и о(х), то он должен быть равен 8сб(и(х),е(х)) в соответствии с (24). С другой стороны, если он не делит и(х) и и(к), то с)ей(д) > де8(о). Из алгоритма 4.6.1Е следует, что этот случай возможен, только если р делит старший коэффициент одного из ненулевых остатков, вычисленных по этому алгоритму с использованием точной целой арифметики; в противном случае алгоритм Евклида по модулю р работает с той же последовательностью полнномов, что и алгоритм 4.6.1Е, за исключением кратности ненулевой константе (по модулю р). Только малое число "неудачных" целых чисел может привести к отсутствию наибольшего общего делителя, и если продолжить попытки, то вскоре можно будет найти "удачное" простое число.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
