AOP_Tom2 (1021737), страница 136
Текст из файла (страница 136)
Для получения следующих строк матрицы Я можно вычислить хэ" гоаб и(х), хв" шой и(х), ..., выполнив многократное умножение на хв пюб и(х) аналогично возводению в квадрат по модулю и(х). Шаг В2 завершается за О(пв(!ойр)э) дополнительных единиц времени.
Таким образам, шаги В1-В3 требуют в сумме 0(пэ(!ойр)в + пв(!обр)э) единиц времени: эти три шага позволяют получить количество делителей и(х). Но на шаге В4 необходимо вычислить наибольший общий делитель для р различных значений в, что очень сложно даже при умеренно больших значениях р. Впервые это пропятствие было преодолено Гансом Зассенхаузом (Наив ЕаввепЬаив) (Х Уишбег ТЛеогу 1 (1969), 291 — 311), которьсй показал, как определить все "полезные" значения в (см. упр, 14).
Еще лучший путь был найден Зассенхаузом и Кантором (Сансах) в 1980 году. Если и(х) представляет собой некоторое решение (8), то и(х) делит о(х)в — и(х) = и(х) (и(х)!" 'и'+1) (и(х)!в 'пэ — 1). Предполагается, что мы вычисляем 8са(и(х), и(х)!" ~~ — 1); (20) при неболыпом везении (20) будет нетривиальным множителем и(х). В действительности можно точно определить нужную степень везения, рассмотрев (7). Пусть и(х) ив в в по модулю р,(х) для 1 < у < г. В таком случае р,(х) делит и(х)!" 'н~ — 1 тогда и только тогда, когда в~" !7 ш 1 па модулю р. Известно, что в точности (р — 1)/2 целых в в диапазоне 0 < в < р удовлетворяют условию в!э 07э э— а 1 (по модулю р); следовательно, около половины р,(х) появятся в 8сб (20).
Точнее, если о(х) — случайное решение (8), где все р' решений равновероятны, вероятность того, что 8сс! (20) равен и(х), в точности равна ((р — Ц7гр)', а вероятность, что это равно 1, составляет ((р+ 1)/2р)'. Вероятность получения нетривиального множителя будет, таким образом, равна -('=')'-('— ,")'= — — '- ("(') "(') "-)-'~ для всех г > 2 и р > 3. Таким образом, неплохой идеей является замена шага В4 следующей процедурой (кроме случаев, когда р мало): установить и(х) +- п1о!')(х)+пэи(э)(х)+ .+а,и")(х), где коэффициенгы а.
выбраны случайно в диапазоне 0 < а < р. Пусть текущее частичное разложение и(х) представляет собой ив (х)... ир(х), где Ф изначально равно 1. Вычислим д,(х) = 8сб(и;(х), о(х)!в 07э — 1) для всех 1, таких, что бей(и) > 1; заменим и(х) над(х) (и(х)/д(х)) и будем увеличивать значение ! после каждого найденного нетривиального йсб. Будем повторять процесс для различных вариантов о(х) до тех пор, пока не получим 1 = г. Если предположить, что потребуется всего О(!ойг) случайных решений с(х) уравнения (8) (что вполне допустимо), то можно указать верхнюю границу времени, необходимого для выполнения этой альтернативы шагу В4.
Она требует 0(гп(!ойр) ) шагов для вычисления о(х), 0(~(з(!ойр)з) шагов для вычисления о(х)!" ~!7~ шоб и,(х) (если с1ей(и,) = Н) и 0(<1з(!ойр) ) шагов для поиска йсо(гм(х),е(х)!г В~э — 1). Таким образом, общеевремя составляет О(пз(!ойр) !ойг). Разложение с различными степенями. Теперь обратимся к несколько более простому пути поиска разложения по модулю р. Изложенные в этом разделе идеи включают множество поучительных обращений к вычислительной алгебре, и автор не извиняется перед чи тателем за ик количество. Однако проблема разложения по модулю р фактически может быть решена без обращения к множеству концепций.
Во-первых, можно использовать тот факт, что неприводимый полинам д(х) степени Н является делителем хг — х и не является делителем хг — х для 1 ( с < Н (см. упр. 16). Таким образом, можно исключить неприводимые множители каждой степени раздельна, выбрав следующую стратегию. П1. Исключить квадратныо множители, как в алгоритме Берлекампа. Установить также с(х) +- и(х), ю(х) < — "х" и Н ( — 0 (здесь с(х) и ю(х) — -переменные, имеющие в качестве значений полиномы), П2. (Сейчас и>(х) = х" шоб о(х); все веприводимые множители с(х) различны и имеют степень > Н.) Если 0+1 > 1 бей(о), выполнение процедуры прекращается, поскольку либо е(х) = 1, либо е(х) — неприводимый полипом.
В противном случае увеличить и' на 1 и заменить ю(х) на ю(х) г шоб и(х). ПЗ. Найти дэ(х) = йсп(ю(х) — х, о(х)). (Это произведение всех неприводимых множителей и(х), степени которых равны Ы.) Если дэ(х) ф 1, заменить о(х) на о(х)/дэ(х) и ю(х) на ю(х) шоб о(х). Если степень дэ(х) больше, чем Н, использовать приведенный ниже алгоритм для поиска его множителей. Вернуться к шагу 02. Эта процедура позволяет определить произведение всех неприводимых множителей со степенью Н и таким образом выяснить, сколько существует множителей конкретной степени. Поскольку три множителя в нашем примере полинома (19) имеют различные степени.
все они могут быть найдены без разложения полиномов дэ(х). Для завершения метода необходим путь, предоставляющий возможность разделить полинам дэ(х) па неприводимые множители, когда бей(дэ) > Н. Майкл Рабин (М!сЬае! ВаЬ!и) в 1976 году доказал, что это можно сделать при помощи арифметических операций в поле из р~ элементов. Дэвид Д, Кантор (Паг!и О. Сапнн) и Ганс: Зассенхауз (Наив ХаввспЬацз) открыли в 1979 голу, что существует еще более простой путь, основанный на следующем тождестве: если р — некоторое нечетное простое число, то имеем дэ(х) = йсй(дэ(х) 1(х)) йсб(дэ(х), 1(х)!" 'Ь +1) йсг!(дэ(х),1(х)!г '1~ — 1) (21) для всех полиномов !(х), поскольку 1(х)г — !(х) кратно всем неприводимым полиномам степени Ы (1(х) можно рассматривать как элемент поля размером р, когда такое поле состоит из всех полиномов по модулю неприводимого » (х), как в упр.
16). В упр. 29 показано, что 8сс!(дз(х), г(х)(я'-»)/з — 1) будет нетривиальным множителем дэ(х) примерно в половине случаев, если 1(х) — случайный поливом степени < 2»4 — 1; следовательно, не придется предпринимать множество случайных попыток, чтобы найти все делители. Без потери общности можно положить, что Ф(х) нормирован, поскольку целые кратные 1(х) не приводят к отличиям, кроь»е возможного изменения знака 1(х)»г -»уз Таким образом, когда»! = 1, можно получить 1(х) = х+», где в выбрано случайно.
Иногда эта процедура будет в действительности успешной для»» > 1, когда используются только линейные полиномы 1(х). Например, имеется восемь неприводимык полиномав Дх) степени 3 по модулю 3 и для всех из них по-разному вычисляются 8с»!(1(х), (х+ в)»з — 1) для 0 < в < 3. У( ) в=О э=1 в=2 х»+ 2х+ 1 1 1 1 хз + 2х + 2 Дх) У(х) Дх) хз + хг + 2 7(х) 1(х) 1 хр + хз + х + 2 /(х) 1 1(х) х' Ч- х' Ч- 2х Ч- 1 1 1(х) )(х) хз + 2хз + 1 1 ~(х) 1 хз+2хз+ х+1 1 1 Дх) ха+ 2хз+2хЧ-2 у(х) 1 1 В упр. 31 частично объясняется, почему линейные полиномы могут оказаться эффективными; однако, когда количество неприводимык полиномов степени»» превышает 2г, я»:но, что будут существовать непрнводимые полнномы, неразличимые посредством линейного выбора !(х). Альтернатива для (21), которая работает при р = 2, обсуждается в упр. 30.
Болев быстрый алгоритм разложения с различными степенями при очень больших р был найден Э, Калтофеном (Е. Ка!со1еп) и В. Шаупом (1». Я!»оир); время его работы составляет 0(пэ э + и'" ' !ойр) арифметических операций по модулю р для чисел практпческого размера и 0(п!'+ 0»4 !обр) таких операций при и -+ со, когда ь» является степенью "быстрого" умножения матриц в упр. 4.6.4-66. (См. ».
БутЬо!!с Сошр. 20 (1995), 363-397; Ма»!». Сотр. 67 (1998), 1179 — 1197.) Ис»порические справки. Идея поиска всех линейных множителей свободного от квадратов полинома Дх) по модулю р посредством вычисления сначала д(х) = 8с»!(х' ' — 1, »(х)), а затем -8с»!(д(х), (х+в)»Я»»»'х1) для произвольного э была высказана й. М. Лежандром (Л. М. Ьейеп»!ге), Ме»поп.еэ Асад, Ясй Рагтэ (1785), 484- 490.
Поводом к этому послужил поиск всех целых решений Диофантовых уравнений вида 7'(х) = ру, т. е, У(х) = 0 (по модулю р). Более общая технология разделенна степеней, воплощенная в алгоритме В, была открыла сначала К. Ф. Гауссом (С. Г. Сапээ) до 1800 года, но не публиковалась [см. его !4гег)»е 2 (1876), 237), а затем — Эваристом Галуа (Е»апэ»е Са!сйэ) в классической ныне работе, ставшей основой теории конечных полей (Ви1!ебп»!еэ Бс!е»»сея Ма!!»е»пабйиез, Р!»уз!9»»еэ е» СЬишдиеэ 13 (1830), 428-435; перепечатана в Х»)е Май.
Ригеэ е» Аррййиеев 11 (1846), 398-407]. Однако эти работы Гаусса и Галуа опередили свое время и не были поняты, пока Дж. А, Серре (3. А. Яеггег) не дал детальное толкование насколько позже [Метло!гев Асад. Яс!. Рапв, вег!ев 2, 35 (1866), 617 — 688; алгоритм П находится в 17]. Специальные процедуры для разделения дв(х) на неприводимые множители были разработаны последовательно различными авторами, однако универсальный метод, который оставался бы эффективным при больших р, по-иидимому, не был открыт до появления компьютеров, потребовавших его разработки. Первый такой рандамизированный алгоритм со строгим анализом времени рабаты был опубликован Берлекампом [Е. Вег!е1гавпр, МайЛ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
