AOP_Tom2 (1021737), страница 138
Текст из файла (страница 138)
упр. 26). Можно представить В, в виде строки из и битов. Теперь вычислим пересечение [) Вм т. е. побитовое Айй этих строк, и выполним шаг Г2 только для Йей(1~) + . + Йей(1э) Е () 11з. Кроме того, р выбирается таким образом, чтобы р. имело наименьшее значение г. Эта технология разработана Дэвидом Р. Мюссером (Павий В. Мпввег), который, исходя из своего опыта, предложил испытывать около пяти простых чисел ру [см.
зАСМ 25 (1978), 271-282). Конечно, следует немедленно остановиться, если текущее пересечение () В, показывает. что полином и(х) является неприводимым. Мюссер привел полное обсуждение метода разложения, подобного описанному выше, в .7АСМ 22 (1975), 291 — 308. Шаги Г1-ЕЗ объединяются в усовершенствованном варианте, предложенном в 1978 году Дж. Э. Коллинзом (6. Е.
Со)йпэ). Он заключается в поиске пробных делителей путем одновременного получения комбинаций из 0 множителей вместо комбинаций с общей степенью Н. Это усовершенствование важно в связи со статистическим поведением множителей полиномов по модулю р, которые неприводимы над полем рациональных чисел (см. упр. 37). А. К. Ленстра (А. К. Ьепэтга), Х. В. Ленстра (мл.) (Н. Ж. Ьепэтга, Лг.) и Л. Ловас (Ь.
Ьочаэх) предложили свой известный "ЬЬЬ-алгоритм" разложения полинома над кольцом целых чисел с точными границами количества вычислений в худшем случае [МаВь Аппа!еп 261 (1982), 515 — 534). Их метод не требует случайных чисел, а время его работы для полинома и(х) степени п составляет 0(п" + п~(1об)~и)!) ) битовых операций, где ~)ий определяется в упр. 20. Эта оценка включает время поиска подходящего простого числа р и всех множителей по модулю р при помощи алгоритма В.
Конечно, эвристические методы, использующие рандамнзацию, на практике работают значительно быстрее, Наибольшие общие делители. Подобные технологии могут применяться и для вычисления наибольших общих делителей полиномов; если ясд(и(х), е(х)) = 4х) нэд кольцом целых чисел и если 8са(и(х), е(х)) = д(х) (по модулю р), где д(х)— нормированный полинам, то Н(х) является общим делителем и(х) и е(х) по модулю р; следовательно, И(х) делит д(х) (по модулю р). (24) Если р не делит старшие коэффициенты ни и, ни е, то р не делит и старший коэффициент 4 в таком случае бей(Н) < йеб(д).
Если для такого простого р 9(х) = 1, то пей(п) = 0 и Ы(х) = йсп(санс(и), санс(е)). Это подтверждает сделанное в разделе 4.6.1 примечание о том, что простого вычисления йод(и(х), е(х)) по модулю 13 в 4.6.1 — (6) достаточно для доказательства того, что и(х) и е(х) взаимно просты над кольцом целых чисел; тем самым сравнительно трудоемких вычислений согласно алгоритму 4.6.1Е или 4.6.1С можно избежать. Поскольку два случайных примитивных полннома почти всегда взаимно прогты над кольцом целых чисел и поскольку они взаимно просты по модулю простого числа р с вероятностью 1 — 1/р в соответствии с упр. 4.6.1-5, вычисления обычно стоит производить по модулю р. Как отмечалась ранее, нужны хорошие методы и для неслучайных полиномов, встречающихся на практике.
Таким образам, мы хотим улучшить свои методы и научиться находить йсб(и(х),е(х)) в общем случае над кольцом целых чисел, основываясь только на информации, которая была получена при рабоче по модулю простых чисел р. Можно считать, что и(х) и е(х) — примитивные полиномы. Вместо непосредственного вычисления йси(и(х), е(х)) удобнее искать полинам сХ(х) = с йсй(и(х), е(х)), (25) где констанза с выбирается таким образом, что г(й) = Ксп(с(и),т(е)).
(26) Выбрав подходящее с, можно всегда достичь выполнения данного условия, поскольку старший коэффициент любого общего делителя и(х) и е(х) должен быль делителем 8сд(с(и),Р(е)). Как только будет найден Й(х), удовлетворяющий этим условиям, можно будет легко вычислить рр(й(х)), который и является истинным наиболыпим общим делителем и(х) и е(х). Условие (26) удобно тем, что позволяет избежать неопределенности кратности наибольшего общего делителя обратимым элементам; использовалась, по существу, та же идея для контроля над старшими коэффициентами в программе разложения на множители. Если р — достаточно большое простое число, которое основано на границах коэффициентов из упр.
20, приложенных к г(Й) и(х) либо к 5(й)и(х), вычислим единственный полипом д(х) = 1(Й)д(х) (по модулю р), все коэффициенты которого находятся в диапазоне ( — -'р.. -'р). Если рр(4(х)) делит как и(х), так и и(х), то он должен быть равен 8сй(и(х),и(х)) в соответствии с (24). С другой стороны, если он не делит и(х) и и(х), то бе8(д) > бе8(и). Из алгоритма 4.6.1Е следует, что этот случай возможен, только если р делит старший коэффициент одного из ненулевых остатков, вычисленных по этому алгоритму с использованием точной целой арифметики; в противном случае алгоритм Евклида по модулю р работает с той же последовательностью полиномов, что и алгоритм 4.6.1Е, за исключением кратности ненулевой константе (по модулю р).
Только малое число "неудачных" целых чисел может привести к отсутствию наибольшего общего делителя, и если продолжить попытки, то вскоре можно будет найти "удачное" простое число. Если граница коэффициентов настолько велика, что простых чисел р с однократной точностью недостаточно, можно вычислять Й(х) по модулю нескольких простых чисел р, пока она не будет определена с помощью алгоритма на основе китайской теоремы об остатках из раздела 4.3.2.
Такой подход, предложенный В. С. Брауном (1т'. 8. Вгони) и Дж. Э. Коллинзом, детально описан в УАСЪ| 18 (1971), 478-504. Кроме того, как рекомендуется в работе Я. Моэеэ апй В. У. У. Уип, Ргос. АСМ Сопб 28 (1973), 159 — 166, можно использовать для определения И(х) по модулю р' для достаточно больших е метод Хенселя. Построение Хенселя выглядит с точки зрения вычислений превосходящим подход с использованием китайской теоремы об остатках, но непосредственно это верно только при (27) и(х) 1 и(х)/Н(х) или й(х) .~. и(х)/д(х), поскольку идея заключается в применении методик из упр. 22 к одному из разложений 5(И) и(х) = д(х)и, (х) или г(д)и(х) = 4(х)и,(х) (по модулю р).
В упр. 34 и 35 показано, чао при необходимости с помощью перестановки можно выполнить (27). (Запись (28) и(х) .~ и(х), использованная в (27), означает, что и(х) и и(х) взаимно просты, по аналогии с обозначением, применяемым для взаимно простых чисел.) Алгоритм наибольшего общего делителя, наброски которого приведены в этом разделе, выполняется значительно быстрее алгоритма из раздела 4.6.1 за исключением случая, когда последовательность полиномиальных остатков очень коротка.
Возможно, лучшая обобшенная процедура должна начинаться с вычисления 8со(и(х), и(х)) по модулю небольшого простого числа р, не являющегося одновременно делителем г(и) и г(и). Если получен результат д(х) = 1, мы завершаем работу; если же он имеет высокую степень, используем алгоритм 4.6.1С. В противном случае применяем один из описанных выше методов, сначала вычисляя границу коэффициентов Ы(х) на основе коэффициентов и(х) и и(х) и малой степони полинома д(х). Как и в задаче разложения на множители, если младшие коэффициенты полиномов проще старших, необходимо применить эту процедуру к "обращенным" полиномам и(х), и(х) и обратить полученный результат. Полнномы от многих переменных. Подобные методы приводят к алгоритмам, применимым для разложения на множители или поиска наибольших общих делителей полиномов от нескольких переменных с целыми коэффициентами.
С полиномом и(хс,..., хс) удобно работать по модулю неприводимых полиномов хэ — аэ,..., хс — ас, играющих в данном случае роль р из рассматривавшегося ранее материала. Поскольку и(х) снос( (х — а) = и(а), значение и(хс,..., хс) спосс (хэ — аэ,..., хс — ас) является полиномом от одной переменной и(хс, аэ,, ас). Если целые числа аэ,...,ас выбраны так, что и(хс, аэ,..., а,) имеет ту же степень хс, что и исходный полинам и(хс, хэ,..., х,), подходящее обобщение построения Хенселя "поднимет" свободные от квадратов разложения этого полинома от одной переменной к разложениям по модулю ((хэ — аэ)"', ..., (хс — ас)гч ), где и, — степень ху в и.
В то же время можно работать и по модулю подходящего целого простого числа р. Чтобы сохранялась разреженность промежуточных результатов, как можно большее количество ау должно быть нулевым. Дополнительная информация приводится в упоминавшойся в этом разделе статье, а также в Р. 8. Исапб, Ма1)с. Сошр. 32 (1978), 1215-1231. Со времен первых пионерских статей, процитированных выше, накоплен значительный вычислительный опыт. Для ознакомления с ним рекомендуется обратиться к работе К.
Е. 21рре1, Естессп е Ро)упоппа! Сосссрпса1)осс (Возсоп: К1иэтег, 1993), в которой приведен обзор последних важных публикаций. Кроме того, в настоящее время возможно разложение полиномов, даваемых неявно вычислительной процедурой "черного ящика", даже если они, будучи записанными явным образом, заполнят всю Вселенную [см. Е. Ка11оГеп апс1 В.
М. Тгайег, е. Яушбо)сс Соспр. 9 (1990), 301-320; У. Х. Еа1сэйпэап апс) В. Пахьй Яаппс(егэ, ЯСОМР 24 (1995), 387-397[. Аснмототнческк лучшие алгоритмы зачастую оказываются наихудшим решением дкя всех задач, к которым онн применимы. — д. д.
кднтор (о. и. сдмтон) н Г. ЗДССЕСЧХДэгЗ ГН. гДВВНССНДССВ) (СВВС1 УПРАЖНЕНИЯ 1. (Мзз) Пусть р — простое число и пусть и(х) — случайный полипом степени и. Считаем, что все р" нормированных полиномов равновероятны. Покажите, что, если и > 2, вероятность того, что и(х) имеет линейный множитель по модулю р, находится между (1+р ')/2 и (2+р )/3 включительно. Приведите точный внл этой вероятности при п > р. Чему равно среднее количество линейных множителей? 2.
[Мйв] (а) Покажите, что любой нормированный полинолс и(х) над областью единственного разложения может быть единственным образом представлен в виде и(х) = о(х) ис(х), гле ис(х) свободен от квалратов (не имеет множителей положительной степени вида с1(х) ) 2 и оба полинома с-в(х) и ш(х) — нормированы. (Ь) (Э. Р. Верлекамп (Е. К. Вет1е1сашр).) Сколько нормированных полиномов степени п свободны от квадратов по модулю р, где р — простое число? 3. [М28] (Китааская теорема од остагпках для аоликомоо.) Пусть ие(х),..., и,(х)— полиномы над пачем Я, где и (х) д. иа(х) для всех 2 ф?е. Докажите, что для любых данных полиномов юе(х), ..., ю,(х) над Я имеется единственный полинам о(х) над л, 'такой, что е1еб(о) < деб(ив) + . + деб(и,.) и о(х) = ай(х) шее?и,(х) для 1 < д < г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
