с помощью O(logp) операций возведения в квадрат по модулю и{х), т. е. переходов от ж* mod и{х) к х* mod и{х), совместно с операциями умножения на х. Операция возведения в квадрат вьшолняется относительно просто, если сначала создать вспомогательную таблицу значений х™ modw(x) для т = п, п + 1, ..., 2п - 2. Если х mod и{х) = Cn-ix"~ +----h cix + cq, to

x* mod u{x) = (c jx2"-2 + ... + (cico -b ciCo)x + Cq) mod u{x),

где x2""2, ..., x" могут быть заменены полиномами из вспомогательной таблицы. Общее время вычисления xmodM(x) сводится к 0[n(logp)) единицам, и мы получаем вторую строку матрицы Q. Для получения следующих строк матрицы Q можно вычислить хР mod и(х), х mod и(х), ..., выполнив многократное умножение на xmodw(x) аналогично возведению в квадрат по модулю и(х). Шаг В2 завершается за 0(n(logp)2) дополнительных единиц времени. Таким образом, шаги В1-ВЗ требуют в сумме 0(n2(logp) + n{logp)) единиц времени; эти три шага позволяют получить количество делителей ы(х).

Но на шаге В4 необходимо вычислить наибольший общий делитель для р различных значений s, что очень сложно даже при умеренно больших значениях р. Впервые это препятствие было преодолено Гансом Зассенхаузом (Hans Zassenhaus) [J. Number Theory 1 (1969), 291-311], который показал, как определить все "полезные" значения s (см. упр. 14). Еще лучший путь был найден Зассенхаузом и Кантором (Cantor) в 1980 году. Если v{x) представляет собой некоторое решение (8), то и(х) делит v{x) - v{x) = v{x) («(х)"/ i). (t;(a;)(P~i)/2 - l). Предполагается, что мы вычисляем

gcd(w(x), г;(х)(-1/2 1); (20)

при небольшом везении (20) будет нетривиальным множителем и(х). В действительности можно точно определить нужную степень везения, рассмотрев (7). Пусть v{x) = Sj по модулю pj{x) для I < j <г. в таком случае Pj{x) делит «(х)"/ i тогда и только тогда, когда sf = 1 по модулю р. Известно, что в точности (р - 1)/2 целых S в диапазоне О < s < р удовлетворяют условию s/ = j (по модулю р); следовательно, около половины pj{x) появятся в gcd (20). Точнее, если v{x) -случайное решение (8), где все р решений равновероятны, вероятность того, что gcd (20) равен и(х), в точности равна

((p-l)/2p)

а вероятность, что это равно 1, составляет [{р + 1)/2рУ. Вероятность получения нетривиального множителя будет, таким образом, равна

для всех г > 2 и р > 3.

Таким образом, неплохой идеей является замена шага В4 следующей процедурой

(кроме случаев, когдар малб): установить v{x) •(- aiv{x)+a2V{x)-\-----haruM(x),

где коэффициенты Uj выбраны случайно в диапазоне О < а- < р. Пусть текущее частичное разложение и(х) представляет собой ui{x)... щ{х), где t изначально равно 1. Вычислим

giix)gcd{uiix),vix)P-y -1)

для всех г, таких, что deg(wj) > 1; заменим щ(х) на gi(x)-[ui{x)/gi{x)) и будем увеличивать значение t после каждого найденного нетривиального gcd. Будем повторять процесс для различных вариантов v{x) до тех пор, пока не получим t = г.

Если предположить, что потребуется всего O(logr) случайных решений v{x) уравнения (8) (что вполне допустимо), то можно указать верхнюю границу времени, необходимого для вьшолнения этой альтернативы шагу В4. Она требует 0(rn(logp)) шагов для вычисления v{x), 0(d(logp)) шагов для вычисления v{x)P~> mod Ui{x) (если deg(wi) = d) и 0(d(logp)) шагов для поиска gcd(wi(a;), v{x)-~>-l). Таким образом, общее время составляет 0(n(logp) logr).

Разложение с различными степенями. Теперь обратимся к несколько более простому пути поиска разложения по модулю р. Изложенные в этом разделе идеи включают множество поучительных обращений к вычислительной алгебре, и автор не извиняется перед читателем за их количество. Однако проблема разложения по модулю р фактически может быть решена без обращения к множеству концепций.

Во-первых, можно использовать тот факт, что неприводимый полином q{x) степени d является делителем хр"" - а; и не является делителем хР° - х для 1 < с < d (см. упр. 16). Таким образом, можно исключить неприводимые множители каждой степени раздельно, выбрав следуюшую стратегию.

D1. Исключить квадратные множители, как в алгоритме Берлекампа. Установить также v{x) <г- и{х), w{x) +- "а;" и d О (здесь v{x) и w{x) - переменные, имеющие в качестве значений полиномы).

D2. (Сейчас w{x) = х modv{x); все неприводимые множители v{x) различны и имеют степень > d.) Если d+ 1 > deg(w), выполнение процедуры прекращается, поскольку либо v{x) = 1, либо v{x) -неприводимый полином. В противном случае увеличить d на 1 и заменить w{x) на w{xY mod v(x).

D3. Найти gd{x) = gcd(w{x) - x, v{x)). (Это произведение всех неприводимых множителей и{х), степени которых равны d.) Если ffd(a;) ф 1, заменить v{x) на v{x)lgd{x) и w{x) на w{x) modv{x). Если степень gd{x) больше, чем d, использовать приведенный ниже алгоритм для поиска его множителей. Вернуться к шагу D2. I

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

Для завершения метода необходим путь, предоставляющий возможность разделить полином gd{x) на неприводимые множители, когда deg(pd) > d. Майкл Рабин (Michael Rabin) в 1976 году доказал, что это можно сделать при помощи арифметических операций в поле из р"* элементов. Дэвид Д. Кантор (David G. Cantor) и Ганс Зассенхауз (Hans Zassenhaus) открыли в 1979 году, что существует еще более простой путь, основанный на следующем тождестве: если р - некоторое нечетное простое число, то имеем

gd{x) = gcd{gdix), tix)) gcd{gdix), 1{х"~У +1) gcd(pd(a;), tixf- -1) (21)

для всех полиномов t{x), поскольку ЦтУ"" - t{x) кратно всем неприводимым полиномам степени d {t{x) можно рассматривать как элемент поля размером р, когда такое поле состоит из всех полиномов по модулю неприводимого f{x), как в упр. 16). В упр. 29 показано, что gcd(gd(ж), t(a;)(p-i)/2-l) будет нетривиальным множителем gd{x) примерно в половине случаев, если t{x) -случайный полином степени < 2d- 1; следовательно, не придется предпринимать множество случайных попыток, чтобы найти все делители. Без потери общности можно положить, что t{x) нормирован, поскольку целые кратные t{x) не приводят к отличиям, кроме возможного изменения знака t{x)iP -i)/2. Таким образом, когда d = 1, можно получить t{x) = х + s, где S выбрано случайно.

Иногда эта процедура будет в действительности успешной для d > 1, когда используются только линейные полиномы t{x). Например, имеется восемь неприводимых полиномов f{x) степени 3 по модулю 3 и для всех из них по-разному вычисляются gcd(/(x), {х + s) - 1) для О < S < 3.

В упр. 31 частично объясняется, почему линейные полиномы могут оказаться эффективными; однако, когда количество неприводимых полиномов степени d превышает 2, ЯСНО; что будут существовать неприводимые полиномы, неразличимые посредством линейного выбора t{x).

Альтернатива для (21), которая работает при р = 2, обсуждается в упр. 30. Более быстрый алгоритм разложения с различными степеня.ми при очень больших р был найден Э. Калтофеном (Е. Kaltofen) и В. Шаупом (V. Shoup); время его работы составляет Oiji- + logp) арифметических операций по модулю р для чисел практического размера и 0(п("""+/ logp) таких операций при тг оо, когда UJ является степенью "быстрого" умножения матриц в упр. 4.6.4-66. [См. J. Symbolic Сотр. 20 (1995), 363-397; Math. Сотр. 67 (1998), 1179-1197.]

Исторические справки. Идея поиска всех линейных множителей свободного от квадратов полинома /(х) по модулю р посредством вычисления сначала д{х) - gcd(x" - 1, fix)), азатем - gcd(p(x), (x-l-s)(~/2±l) для произвольного s была высказана А. М. Лежандром (А. М. Legendre), Memoires Acad. Sci. Paris (1785), 484-490. Поводом к этому послужил поиск всех целых решений Диофантовых уравнений вида /(х) = ру, т. е. /(х) = О (по модулю р). Более общая технология разделения степеней, воплощенная в алгоритме D, была открыта сначала К. Ф. Гауссом (С. F. Gauss) до 1800 года, но не публиковалась [см. его Werke 2 (1876), 237], а затем - Эваристом Галуа (Evariste Galois) в классической ныне работе, ставшей основой теории конечных полей [Bulletin des Sciences Mathematiques, Physiques et Chimiques 13 (1830), 428-435; перепечатана в J. de Math. Pures et Appliquees 11