Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 30
Текст из файла (страница 30)
Если граница коэффициентов настолько велика, что простых чисел р с однократной точностью недостаточно, можно вычислять фх) по модулю нескольких простых чисел р, пока она не будет определена с помощью алгоритма на основе китайской теоремы об остатках из раздела 4.3.2. Такой подход, предложенный В. С. Брауном (%. 8. Вгоэгп) и Дж. Э. Коллинзом, детально описан в,уАСМ 18 (1971), 478-504.
Кроме того, как рекомендуется в работе 3. Моэеэ апб О. У, У. Ъ'пп, ггос. АСМ Сопб 28 (1973), 159 — 166, можно использовать для определения Й(х) по модулю р' для достаточно больших е метод Хенселя. Построение Хенселя выглядит с точки зрения вычислений превосходящим подход с использованием китайской теоремы об остатках., но непосредственно это верно только при (27) 8(х) .1 и(х)/8(х) нли 8(х) .1 о(х)/4х), поскольку идея заключается в применении методик из упр. 22 к одному из Разложений 4(сХ) и(х) = 4(х) м~ (х) или К(сК) е(х) ги 4(х) о~ (х) (по модулю р), В упр. 34 и 35 показано, что при необходимости с помощью перестановки можно выполнить (27).
(Запись (28) и(я) 1. е(х), использованная в (27), означает, что п(х) н е(т) взаимно просты, по аналогии с обозначением, применяемым для взаимно простых чисел.) Алгоритм наибольшего общего делителя, наброски которого приведены в этом разделе, выполняется значительно быстрее алгоритма из раздела 4.6.1 за исключением случая, когда последовательяость полиномивльных остатков очень коротка. Возможно, лучшая обобщенная процедура должна начинаться с вычисления 8сй(и(к), о(х)) по модулю небольшого простого числа р, не являющегося одновременно делителем 4(и) и 8(с). Если получен результат д(х) = 1, мы завершаем работу; если же он имеет высокую степень, используем алгоритм 4.6.1С.
В противном случае применяем один из описанных выше методов, сначала вычисляя границу коэффициентов фх) на основе коэффициентов и(х) и в(х) н малой степени полинома 4(х). Как и в задаче разложения на множители, если младшие коэффициенты полиномов проще старших, необходимо применить эту процедуру к "обращенным" полнномам и(х), и(х) и обратить полученный резушьтат. Полиномы от многих переменных. Подобные методы приводят к алгоритмам, применимым для разложения на множители или поиска наибольших общих делителей полиномов от нескольких переменных с целыми коэффициентами.
С полиномом и(хс,..., хс) удобно работать по модулю неприводнмых полиномов хз- аз, „хс- ас, играющих в данном случае роль р из рассматривавшегося ранее материала. Поскольку о(х) шос)(х-а) = о(а), значение и(хм...,хс) шоб (хс — аю" хс — ас) является полиномом от одной переменкой и(хс, аз,..., ас). Если целые числа ас, . ° ас выбраны так, что и(хс, аз,..., ас) имеет ту же степень хс, что и исходный полинам и(хс, хт,..., хс), подходящее обобщение построения Хенселя кподнимет" свободные от квадратов разложения этого полинома от одной переменной к разложениям по модулю ((хт — аз)"', ..., (х, — ас)™ ), где и — степень ху в и.
В то же время можно работать и по модулю подходящего целого простого числа р. Чтобы сохранялась разреженность промежуточных результатов, как можно большее количество а должно быть нулевым. Дополнительная информация приводится в упоминавшейся в этом разделе статье, а также в Р. Б. %влб, МагЬ. Сошр. 32 (1978), 1215-1231. Со времен первых пионерских статей, процитированных выше, накоплен значительный вычислительный опыт. Для ознакомления с ним рекомендуется обратиться к работе В. Е. Е(рре), Е)уесВуе Ро1упоппа1 Сшпритабоп (Вовгоп: К1искег, 1993), в которой приведен обзор последних важных публикаций.
Кроме того, в настоящее время возможно разложение полнномов, даваемых неявно вычислительной процедурой "черного ящика", даже если они, будучи записанными явным образом, заполнят всю Вселенную [см. Е. Ка1то1еп впб В. М. Тгайег,,7. Яушбо!)с Сошр. 9 (1990), 301-320; У. ЬЬ Еа[гвЬсиап апс) В. ПатЫ Ваипс)егэ, Б7СОМР 24 (1995), 387-397], дскмптогкческк лучшие злгоркгмы ззчзстую оказываются кзккулшкм оешеккем Лля всех зздзч, к когалым оки применимы. — д, д. кднтОР (О. б, сдм ГОн) к г. здссннхд~гз (н..ъ~бббмндив) 11рвц УПРАЖНЕНИЯ 1. [М24) Пусть р — простое число в пусть и(х) — случайный полинам степени п. Считаем, что все р" нормированных полиномов равновероятны.
Покажите, что, если п > 2, вероятность того, что и(х) имеет линейный множитель ло модулю р, находится между (1+р ')/2 и (2+р ~)/3 включительно. Приведите точныйвндэтой вероятности прил > р. Чему равно среднее количество линейных множителей? 2, [Мко) (а) Покежнте, что любой нормированный полипом и(х) нед областью единственного разложения может быть единственным обрезом представлен в виде где ю(х) свободен от квадратов (не имеет множителей положительной степени вида с1(х) ) и оба полинома — е(х) и ю(х) — нормированы. (Ь) (Э, Р. Берлеквмп (Е.
К. Вег1ейашр).) Сколько нормированных полиномов степени п свободны от квалрвтов по мосйлю р, где р — простое число? 3. [М25] (Китайская теорема об остатках длл полиномое.) Пусть иь(х), ..., и,(х)— полиномы над полем Я, где ид(х) ! иь(х) дчя всех ь ьь х.
Докажите, что для любых данных полиномов юь(х), ..., ю,(х) над о' имеется единственный полинам о(х) над о', 'такой, что деб(о) < с)еб(иь) + + деб(и,) и о(х) ш ю (х) шодиз(х) для ! < у < г. Справедливо ли зто утверждение и в случае, когда Я представляет собой множество всех целых чисел? 4. [НМ88] Пусть а„„вЂ” количество нормироваинмх неприводимых полиномов степени и по модулю простого числа р. Найдите формулу для производящей функции сьр(х) = 2 „а ох".
[Указание. Докажите следующее утверждение, касающееся степенных рядов: 7(х) = ~ ььь д(хь)Д' тогда н только тогда, когда д(х) = ) „>ь Р(п)У(х")/и'.] ЧемУ Равен )ьшр оо а р(р б. [НМЯО] Пусть А„— среднее количество неприволимыхмножителейвыбранногослучайным образом полинома степени и по модулю простого числа р. Покажите, что !пл„,, А„о = Н„, Чему равно предельное среднее значение 2", где г — число неприводимых множителей? 6.
[Мй)] (Ж. Л. Лагранж (1. Ь. Ьабгалбе), 1771.) Докажите тождество (9). [Указание. Разложите хо — х в поле из р элементов.] 7. [МЯУ] Докажите (!4). 8. [НМОО] Как убедиться в том, что векторы, получаемые на выходе алгоритма ь4, линейно независимы? 9. [ОО] Объясните, кисин наипростейшим образом можно построить таблицу обратных величин по модулю 101, если дано, что 2 является первообразным корнем числа 101. ь 10.
[81] Найдите полное разложение по мо,пулю 2 полинома и(х) из (22) с использованием процедуры Берлекампа. 11. [38] Найдите полное разложение полинома и(х) из (22) по модулю б. ь 12. [Мйй] Используйте алгоритм Берлекаьпьа для определения количества множителей и(х) = хс+ 1 по модулю р для всех простых р. [Указание. Рассмотрите случаи, когда р = 2, р = 8)с + 1, р = 81 + 3, р = 8?с + 5, р = 8?с + 7, отдельно. Чему при этом равна матрица сд? Вам не нужно находить множители; требуется найти только их количество.] 13.
[М25] Продолжая предыдущее упражнение, найдите точные формулы для множителей полинома х" + 1 по модулю р для всех нечетных простых чисел р с использованием величин ь/-1, ььс2, ~2, если такие квадратные корни существуют по модулю р. 14. ЬМ85] (Г.
Зассенхауз (Н. Еаыеп)ьаов).) Пусть о(х) — решение (8) и пусть ьо(х) = ][(х — л), где произведение берется по всем 0 < а < р, таким, что 8сс)(и(х), о(х) — о) ~ 1. Объясните, как вычислить ю(х) по данным и(х) и ь(х). [Указание. Из формулы (14) вытекает, что ю(х) является полиномом минимальной степени, таким, что и(х) делит -( (*)) 1' ь 1$.
[Мд?] (Кеадратнис корни ио модулю простака числа.) Разработайте алгоритм для вычисления квадратного корня целого числа и по модулю простого числа р, т. е. найдите число о, такое, что о~ ш и шос1р, если оно существует. Баш алгоритм доллсен быть эффективоьь даже прн очень больших целых числах р. (Для р?1 2 решение этой задачи сводится к ь шению квадратного уравнения по модулю р с использованием обычной квадратььчной формулы.) Указание.
Рассмотрите, что произойдет после применения методов разложения пз этого раздела к папиному х — и. 2 16. [МОО] (Кокс пикс палл.) Назначение данного упражнения — доказать основнью свойства полей, введенных Б. Галуа (Е. Оа)оьз) в 1830 гаду. а) Дано, что 7(х) —.неприводпмый по модулю простого числа р полипом степени и, Докалсите, что р" поляномов степени, меньшей и, образуют поле с арифметикой по модулю 1(х) и р. [Увезенное.
Существование неприводимык полиномов любой степени доказано в упр. 4, поэтому поля с р" элементами существуют для всех простых чисел р и всех и > Ц Ь) Покажите, что любое поле с р" элементами имеет элемент "примитивный корень' б, такой, что элементаии поля являются (О, 1, б, бз,..., бг" -з).
[ухазопое. В упр. 3 2 1 2-16 содержится доказательство для частного случая и = 1.] с) Если у(х) — неприводимый полипом по модулю р степени и, докажите, что хг — х делится на у(х) тогда и только тогда, когда т кратно и. (Отсюда следует, что можно быстро проверить неприводимость. Данный полипом и-й степени 1(х) неприводим по модулю р тогда н только тогда, когда хг — х делится на у(х) н хР ' — х 2 1(х) для всех простых д, которые делят и.) 12.
[Мйу] Пусть à — поле с 13 элементами. Сколько элементов г' имеют порядок у для каждого целого 1 < у < 13зу (Порядком элемента а является нэлмеиъшее положительное целое число щ, такое, что а = 1.) ь 18. [МЯЛ] Пусть и(х) = и„х" + .+по, и„ф 0 является примитивным полиномом с целыми коэффициентами н пусть о(х) — нормированный полипом, определяемый как о(х) = и„в(х/и„) ы х" +о ~х" '+ и„зи„х'" + +поп'„ (а) Дано, что о(х) имеет полное разложение р~(х)...р„(х) над кольцом целых чисел, где каждый ру(х) нормирован. Каково полное разложение полииома и(х) над кольцом целых чисел" .(Ь) Если ю(х) = х + и ~х ~ + + юе является множителем «(х), докажите, что юь является множителем и~ ~ ь при 0 < х < пз.
19. [М80] (Крпщериб Эйэсюятейна.) Возможно, самый известный класс неприводимых полиномов нэд кольцом целмк чисел был введен Т. Шенеманиом (Т. БсЬбпюпавп) в Сгейе 32 (1846), 100, а популяризовав Г. Эйзенштейном (С. Е!зеоэсе1п) в Сге8е 39 (1830), 166-169. Пусть р является простым числом и пусть полинам в(х) = о„х" + + по имеет следующие свойства: (1) п„не делится на р; (й) и„м ..., ко делятся на р, (10) ио не делится на рз. Покавсите, что и(х) неприводим над кольцом целых чисел. 20.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
