ветствующий ы (ж) из списка множителей по модулю р, уменьшить г на число удаленных множителей и завершить работу алгоритма, если d > г. F3. Увеличить d на 1 и вернуться к шагу F2, если d < г.

В заключение этого процесса текущее значение и{х) будет последним неприводимым множителем изначально заданного полинома. Заметьте, что, если uo < u„,

предпочтительно выполнять всю работу с "обращенным полиномом" Uqx" Н-----

множители которого представляют собой "обращенные" множители и{х).

Описанная процедура требует выполнения условия р > 2В, где В - граница коэффициентов любого делителя u„u(i), но можно использовать и гораздо меньшее значение В, если гарантировать, что оно будет верно для делителей степени < deg(u). В этом случае тест на делимость на шаге F2 должен применяться к w{x) =vi{x)... Vr{x)/v{x), а не к v{x) всякий раз, когда deg{v) > deg(u).

Можно еще больше снизить В, если гарантировать, что В ограничивает коэффициенты по меньшей мере одного корректного делителя и(х) (например, при разложении составного целого N вместо полинома некоторые делители могут быть очень большими, но хотя бы один из них будет < VN). Эта идея, предложенная в работе В. Beauzamy, V. Trevisan, P. S. Wang, J. Symbolic Сотр. 15 (1993), 393-413, обсуждается в упр. 21. Проверка делимости на шаге F2 должна в таком случае быть применена и к v{x), и к w{x), но вычисления при этом будут выполняться быстрее, так как р будет иметь гораздо меньшее значение.

Описанный выше алгоритм имеет очевидное слабое место: может возникнуть необходимость в проверке для 2~ - 1 потенциальных множителей v{x). Среднее значение 2 в случайной ситуации составляет порядка п или, возможно, п- (см. упр. 5), но в противном случае понадобится ускорить данную часть программы настолько, насколько это окажется возможно. Один из способов быстрого исключения ложных множителей состоит в первоначальном вычислении младшего коэффициента «3(0) с продолжением, только если он делит £{и)и{0). Сложности, рассмотренные в предыдущих абзацах, не возникают, если это условие делимости не выполнено, поскольку такая проверка корректна даже при deg(t) > deg(u).

Другой важный способ ускорения процедуры состоит в таком уменьшении г, чтобы оно отражало истинное количество множителей. Алгоритм разложения на различные степени, приведенный выше, приложим к различным малым простым числам Pj. Таким образом, для каждого простого числа получается множество Dj возможных степеней множителей по модулюpj (см. упр. 26). Можно представить Dj в виде строки из п битов. Теперь вычислим пересечение C\Dj, т. е. побитовое AND этих строк, и выполним шаг F2 только для

deg(ii) + --- + deg(id)enj-Кроме того, р выбирается таким образом, чтобы pj имело наименьшее значение г. Эта технология разработана Дэвидом Р. Мюссером (David R. Musser), который, исходя из своего опыта, предложил испытывать около пяти простых чисел pj [см. JACM 25 (1978), 271-282]. Конечно, следует немедленно остановиться, если текущее пересечение fl Dj показьшает, что полином и{х) является неприводимым.

Мюссер привел полное обсуждение метода разложения, подобного описанному выше, в JACM 22 (1975), 291-308. Шаги F1-F3 объединяются в усовершенствованном варианте, предложенном в 1978 году Дж. Э. Коллинзом (G. Е. Collins).

Он заключается в поиске пробных делителей путем одновременного получения комбинаций из d множителей вместо комбинаций с общей степенью d. Это усовершенствование важно в связи со статистическим поведением множителей полиномов по модулю р, которые неприводимы над полем рациональных чисел (см. упр. 37).

А. К. Ленстра (А. К. Lenstra), X. В. Ленстра (мл.) (Н. W. Lenstra, Jr.) и Л. Ло-вас (L. Lovasz) предложили свой известный "LLL-алгоритм" разложения полинома над кольцом целых чисел с точными границами количества вычислений в худшем случае [Math. Anna/en 261 (1982), 515-534]. Их метод не требует случайных чисел, а время его работы для полинома и{х) степени п составляет 0[п + n(logu)) битовых операций, где определяется в упр. 20. Эта оценка включает время поиска подходящего простого числа р и всех множителей по модулю р при помощи алгоритма В. Конечно, эвристические методы, использующие рандомизацию, на практике работают значительно быстрее.

Наибольшие общие делители. Подобные технологии могут применяться и для вычисления наибольших общих делителей полиномов: если gcd[u{x),v{x)) = d{x) над кольцом целых чисел и если gcd{u{x),v{x)) - q{x) (по модулю р), где q{x) - нормированный полином, то d{x) является общим делителем и{х) и v{x) по модулю р; следовательно,

d(x) делит q{x) (по модулю р). (24)

Если р не делит старшие коэффициенты ни и, ни v, то р не делит и старший коэффициент d; в таком случае deg(d) < deg(q). Если для такого простого р q{x) = 1, то deg(d) = О и d{x) = gcd(eont(u),cont(u)). Это подтверждает сделанное в разделе 4.6.1 примечание о том, что простого вычисления gcd{u{x),v{x)) по модулю 13 в 4.6.1-(6) достаточно для доказательства того, что и{х) и v{x) взаимно просты над кольцом целых чисел; тем самым сравнительно трудоемких вычислений согласно алгоритму 4.6.1Е или 4.6.1С можно избежать. Поскольку два случайных примитивных полинома почти всегда взаимно просты над кольцом целых чисел и поскольку они взаимно просты по модулю простого числа р с вероятностью 1 - 1 /р в соответствии с упр. 4.6.1-5, вычисления обычно стоит производить по модулю р.

Как ртмечалось ранее, нужны хорошие методы и для неслучайных полиномов, встречающихся на практике. Таким образом, мы хотим улучшить свои методы и научиться находить gcd{u(x),v{x)) в общем случае над кольцом целых чисел, основываясь только на информации, которая была получена при работе по модулю простых чисел р. Можно считать, что и{х) и v{x) -примитивные полиномы.

Вместо непосредственного вычисления gcd[u{x),v{x)) удобнее искать полином

d>)=c-gcd(u(x),i;(x)), (25)

где константа с выбирается таким образом, что

e{d) = gcd{e{u),t{v)). (26)

Выбрав подходящее с, можно всегда достичь вьшолнения данного условия, поскольку старший коэффициент любого общего делителя и{х) и v{x) должен быть делителем gcd[£{u),£{v)). Как только будет найден d{x), удовлетворяющий этим условиям, можно будет легко вычислить pp(d(x)), который и является истинным наибольшим общим делителем и{х) и v{x). Условие (26) удобно тем, что позволяет

избежать неопределенности кратности наибольшего общего делителя обратимым элементам; использовалась, по существу, та же идея для контроля над старшими коэффициентами в программе разложения на множители.

Если р - достаточно большое простое число, которое основано на границах коэффициентов из упр. 20, приложенных к (.{3)и{х) либо к (.{d)v{x), вычислим единственный полином q{x) = i{d)q{x) (по модулю р), все коэффициенты которого находятся в диапазоне [-р..р). Если pp{q{x)) делит как и{х), так и v{x), то он должен быть равен gcd[u{x), v{x)) в соответствии с (24). С другой стороны, если он не делит и{х) и v{x), то deg(q) > deg(d). Из алгоритма 4.6.1Е следует, что этот случай возможен, только если р делит старший коэффициент одного из ненулевых остатков, вычисленных по этому алгоритму с использованием точной целой арифметики; в противном случае алгоритм Евклида по модулю р работает с той же последовательностью полиномов, что и алгоритм 4.6.1Е, за исключением кратности ненулевой константе (по модулю р). Только малое число "неудачных" целых чисел может привести к отсутствию наибольшего общего делителя, и если продолжить попытки, то вскоре можно будет найти "удачное" простое число.

Если граница коэффициентов настолько велика, что простых чисел р с однократной точностью недостаточно, можно вычислять d{x) по модулю нескольких простых чисел р, пока, она не будет определена с помощью алгоритма на основе китайской теоремы об остатках из раздела 4.3.2. Такой подход, предложенный В. С. Брауном (W. S. Brown) и Дж. Э. Коллинзом, детально описан в JACM 18 (1971), 478-504. Кроме того, как рекомендуется в работе J. Moses and D. Y. Y. Yun, Proc. ACM Conf. 28 (1973), 159-166, можно использовать для определения d{x) по модулю р для достаточно больших е метод Хенселя. Построение Хенселя выглядит с точки зрения вычислений превосходящим подход с использованием китайской теоремы об остатках, но непосредственно это верно только при

d{x) 1 u{x)/dix) или d{x) 1 v{x)ld{x), (27)

поскольку идея заключается в применении методик из упр. 22 к одному из разложений (.{d)u{x) = q{x)ui{x) или (.{d)v{x) = q{x)vi{x) (по модулю р). В упр. 34 и 35 показано, что при необходимости с помощью перестановки можно выполнить (27). (Запись

и{х) 1 v{x), (28)

использованная в (27), означает, что и{х) и v{x) взаимно просты, по аналогии с обозначением, применяемым для взаимно простых чисел.)

Алгоритм наибольшего общего делителя, наброски которого приведены в этом разделе, вьшолняется значительно быстрее алгоритма из раздела 4.6.1 за исключением случая, когда последовательность полиномиальных остатков очень коротка. Возможно, лучшая обобщенная процедура должна начинаться с вычисления gcd{u{x),v{x)) по модулю небольшого простого числа р, не являющегося одновременно делителем (.{и) и (.{v). Если получен результат q{x) = 1, мы завершаем работу; если же он имеет высокую степень, используем алгоритм 4.6.1С. В противном случае применяем один из описанных выше методов, сначала вычисляя границу коэффициентов d{x) на основе коэффициентов и{х) и v{x) и малой степени полинома q{x). Как и в задаче разложения на множители, если младшие коэффициенты полиномов