AOP_Tom2 (1021737), страница 140
Текст из файла (страница 140)
[М85] Процедура разложения с различными степенями "удачна", если существует не более одного неприводимого полинама каждой степени 0. Тогда дг(х) никогда не должно разбиваться на множители. Чему равна вероятность такой уда спой ситуации при разложении случайного полинома степени в по модулю р для фиксированного и при р -э аоу 29. [Мдд] Пусть д(х) — произведение двух или более различных неприводимых полиномов степени с( по модулю нечетного простого числа р.
Докажите, что бес)(д(х), 1(х) СР'- с Нэ — 1) будет собственным множителем д(х) с вероятностью > 1/2 — 1/(2р~) для любого фиксированного д(х), когда 1(х) выбрано случайным образом из ры полиномов степени < 20 по модулю р. 30. [М85] Докажите, что если д(х) является неприводнмым полиномом степени 3 по модулю р н если 1(х) является произвольным нолиномом, то значение (С(х) +1(х)в+ 1(х)е'+ . + С(х)э ) щос) д(х) представляет собой целое число (т.
е. полинам степени < 0). Испсьтьзуйте этот факт, чтобы создать рандомизированный алгоритм для разложения дэ(х) в виде произведения неприводимых полиномов степени — с) аналогично (21) для случая, когда р = 2. 31. [НМ30] Пусть р — нечетное простое число и пусть с1 > 1. Пакюките, что существует число п(р, 3), обладающее следующими двумя свойствами. (!) Для всех целых 1 в точности п(р, сс) неприводимых полиномов д(х) степени с1 по модулю р удовлетворяют соотношению (х + 1)Се Псе шос10(х) = 1, (й) Для всех целых чисел О < 1с < Сэ < р в точности п(р, 3) неприводимых полиномов д(х) степени а' по модулю р удовлетворяют соотношению (х+ П)Сг с1сзшос10(х) = (х+С~)Сг'-срэ шос)д(х).
ь 32. [МЯ0] (Цонлотамссчесхое полономьс) Пусть Ф„(х) = П <ь<„ь с„(х — ьс ), где сс = е~ '~". Тогда корни Ф„(х)--.это и-е комплексные корни единицы, не являющиеся т-ми корнями при т < и. а) Докажите, что Ф„(х) — - полинам с целыми коэффициентами и что х" — 1 = П Фл(х); щ (См. упр. 4.5.2 — 10(Ь) и 4.5.3-28(с).) Ъ) Докажите, что полинам Ф„(х) неприводим над кольцом целых чисел Следовательно, предылущая формула является полным разложением х" — 1 над кольцом целых чисел.
[Указание. Если 1(х) является неприводимым множителем Ф„(х) над кольпом целых чисел и если С --комплексное число, для которого 1(С) = О, докажите, что /(Сг) = О для всех простых чисел р, не делящих и. Вам может помочь тот факт, что х" — 1 свободен от квадратов по модулю р для всех таких простых чисел.] с) Обсудите вьсчисление Ф„(х) и протабулируйте значения этой функции для и < 15. ЗЗ. (М!2] Истинно ли следующее утверждение: если и(х) р' О и полное разложение и(х) по модулю р представляет собойрг(х)"...
р,(х)'", топ(х)?Зоб(и(х), и (х)) = рг(х)...р,(х)? ь 34. ]М25] (Разложение, свободное аш кеадратае.) Ясно, что любой примитивный полинам из области единственного разложения может быть выражен в виде и(х) = иг(х) иг(х) из(х)'..., где пшгиномы и,(х) свободны от квадратов н взаимно просты. Такое представление, в котором и, (х) является произведением всех неприводнмых полиномов, делящих и(х) ровно ! рвз, единственно с точностью до обратимого множителя1 это полезный способ представления полиномов, участвующих в умножении, делении и поиске наибольшего общего делителя.
Пусть ССР(и(х), о(х)) представляет собон процедур», которая вычисляет трв значения: ССР(и(х),е(х)) = (а(х),и(х)?д(х),о(х)/д(х)), где д(х) = Зсй(и(х),о(х)). Метод, описанный в тексте раздела, следующем за формулой (25), всегда заканчивается проверочным делением и(х)?а(х) и о(х)/д(х), которое позволяет убедиться, что не было использовано "неудачное" простое число, так что значения и(х)/д(х) и о(х) 74(х) представляют собой побочные продукты вычисления наибольшего общего делителя, т. е. можно вы шслить РСР(и(х) е(х)) с помощью указанного метода так же быстро, как и Зоб(и(х), е(х)). Придумайте процедуру для получения свободного от квадратов представления (иг(х),иг(х),...) данного примитивного полинома и(х) над кольцом целых чисел. Ваш алгоритм дачжен выполнять в точности е вычислений ССР, где е — наибольший индекс, для которого и,(х) ф 1. К тому же каждое вычисление ССР должно удовлетворять условиям (27), чтобы можно было использовать построение Хенселя.
35. ]М22] (Д. Ю. Е. К)нь (Р У. Ъ'. Ъап).) Разработайте алгоритм, вычисляющий свободное от квадратов представление (ил(х), юг(х),...) полинома ю(х) = Зсп(и(х),о(х)) над кольцом целых чисел по свободным от квадратов представлениям (иг(х),иг(х),...) и (ог(х)оег(х),...) полнномов и(х) н о(х). 36. (М27) Расширьтс процедуру упр. 34 так, чтобы получалось свободное от квадратов представление (иг(х), иг(х), ) полннома и(х) с арифметикой коэффициентов, выполняемой по модулю р. З7. [НМ24] (Джордж '3. Коллинз (Реогйе Е. Со!1?пэ) ) Пусть дн ..., д, — положительные целые числа, сумма которых равна и, и пусть р — простое число.
Чему равна вероятность того, что неприводимые множители случайного полинома степени и с целыми коэффициентами имеют при полном разложении по модулю р степени дн ..., д,? Покажите, что асимптотически данная вероятность аналогична вероятности того, что случайная перестановка и элементов имеет циклы длины дн, ф. 33. (НМ27] (Критерий !!еррана.) Пусть и(х) = х" + и„~х" ' + + иа — полинам с целыми коэффициентами, такой, что иа ф О, н либо ]и -г] > 1+ )и„-г]+ +)ие], либо (и з = О н и "г > 1 Ч- ]и -з] + . + ]ие]).
Покажите, что полипом и(х) неприводим над когзьцом целых чисел. (Указание. Докажите, что почти все корни и меньше 1 по абсол ютному значению ] ЗО. (НМ42] (Дэвид Д. Кантор (Ра»нй С Сапгог).) Покажите, что если полинам и(х) неприводнм нэд кольцом целых чисел, то он имеет "укороченное" доказательство неприводнмости в том смысле, что количество битов в доказательстве — это по крайней мере полинам от г1ей(и) и длин коэффициентов. (Здесь требуется граница длины доказательства, как в упр. 4.5.4 — 17, а не граница времени, необходимого для поиска такого доказательства.) Указание.
Если о(х) неприводим и ! является любым полиномом над кольцом целых чисел, то все множители о(с(х)) имеют степень > йей(о). Критерий Перрона дает большой запас ненрнводнмых полнномов о(т). ь 40. (М20] (П. Ш. Ванг (Р. 8. %апй).) Если и„— старший коэффициент полннома и(х) и  — граница коэффициентов некоторого множителя и, то для алгоритма разложения, приведенного в тексте раздела, требуется найти разложение по модулю р', где р' > 2~и, ~В. Но 1и„~ может быть больше, чем В, когда В выбирается по методу нз упр.
21. Покажите, что если полнном и(х) приводим, то существует способ восстановления одного нз его истинных множителей по разложению по модулю р', когда р' > 2Вэ, с помощью алгоритма из упр. 4.5.3-51. 41. (М47) (Бнзамн (Веаоэашу), Тревисан (Тгег!эап) и Ванг (%апб).) Докажите нлн опровергните следующее: существует константа с, такая, что если 7"(х) — некоторый целый полипом с коэффициентами, по абсолютному значению не превосходящими В, то один из его непрнводимых множителей имеет коэффициенты, ограниченные величиной сВ, 4.6.3. Вычисление степеней В этом разделе рассматривается интересная задача — эффективное вычисление х" пэ данным х и и, где и — положительное целое число.
Предположим, например, что необходимо вычислить х'е Можно просто начать с х и 15 раз умножить его на х. Но тот же ответ можно получить всего за четыре умножения, если несколько раз возвести в квадрат получающийся результат, последовательно вычисляя хэ, х4, хэ х1е Эта же идея, в целом, применима к любому значению п следующим образом. Запишем и в виде числа в двоичной системе счисления (убирая нули слева). Затем заменим каждую "1э парой символов ЗХ, каждый "Оэ — символом 8 и вычеркнем крайнюю слева пару символов эЗХ'! Результат представляет собой правило вычисления х", в котором "8" трактуется как операция возведения е кеадрагп, а "Х" — - как операция умнозгсенил на х.
Например, и = 23 имеет двоичное представление 10111. Таким образом, мы формируем последовательность 8Х 88Х БХ БХ, нз которой удаляем начальную пару БХ для получения окончательного правила 88ХБХЗХ. Это правило гласит, что необходимо "возвести в квадрат, возвести в квадрат, умножить на х, возвести в ква;рат., умножить на х, возвести в квадрат и умножить на х', т. е.
последовательно вычислить значения хэ, х4, х', х'о, х", хээ, хээ Этот бинарный метод можно легко обосновать, проанализировав последовательность степеней при вычислении: рассматривая каждое ияэ как операцию умножения на 2, а "Хэ — как операцию прибавления 1 и начав с 1, а не с х, мы придем к вычислению и в соответствии со свойствами двоичной системы счисления. Этот метод очень древний; он полнился до 200 г. до н. э.
в классической индусской Чанда- сутре (СЬапдаЬ-ей!та) Пингалы (Р!пка(а) [см. В. Рат!а апй А. К. 8!пкЬ, Н)эсогу ог" Н!пдп МагЬешаГ!сз 2 (ЕаЬоге: Мог!!а) Вапагэ! Раэ, 1935), 76), Похоже, что в течение следующего тысячелетия этот метод не упоминался нигде за пределами Индии.
В 952 г. и. э. аль-Уклиднси (а1-Пс!116!э!) нз Дамаска четко пояснил, как эффективно вычислить 2" для произвольного и. См. ТЬе Аг!1Ьтес!с оГа)-Н!Ьд!зг Ьу А. 8. ЗаЫап (Рогйгес)э1: Р. Не!йе1, 1975), 341 — 342, где общие идеи проиллюстрированы на примере и = 51. См. также работу аль-Бируни (а1-В1гйщ) СЬгопо!ойу оГАпс!епГ УэаНопз, переведенную н отредактированную Э.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
