AOP_Tom2 (1021737), страница 139
Текст из файла (страница 139)
Справедливо ли это утверждение и в случае, когда 2 представляет собой множество всех целых чисевэ 4. [НМ28] Пусть а р — количество нормированных неприводимых полиномов степени и по модулю простого числа р. Найдите формулу для производящей функции сер(х) 2 „а„рх". [Указание. Докажите следующее утверждение, касщощееся степенных рядов: ,?(х) = 2 .>, д(х)?уч тогда и только тогда, когда д(в) = 2 >, д(п) 7(х")/и] Чему равен йшр а„р?'р ? 5.
[НМЗО] Пусть А„р — среднее количество неприводимых множителей выбранного случайным образом полинома степени и по модулю простого числа р. Покажите, что !пп„„А„р = Н . Чему равно предельное среднее значение 2", где г — число неприводимых множителей? 6. [М21] (Ж, Л. Лагранж (1. Б Ьа8гапбе), 1771.) Докажите тождество (9). [Указание. Разложите хР— х в поле из р элементов.] 7.
[М22] Докажите (14). 8. [НМ20] Как убедиться в гом, что векторы, получаемые на выходе алгоритма?>, линейно независимы? 9. [20] Объясните, каким наипростейшим образом можно построить таблицу обратных величин по модулю 101, если дано, что 2 является первообразным корнем числа 101. ь 10. [21] Найдите полное разложение по модулю 2 полинома и(х) из (22) с использованием процедуры Берлекампа, 11. [22] Найдите полное разложение полинома и(х) из (22) по модулю 5.
Р 12. [М22] Используйте алгоритм Берлекампа для определения количества множителей и(х) = х + 1 по модулю р для всех простых р. [Указание. Рассмотрите случаи, когда 4 р = 2, р = 8?е+ 1, р = 82+ 3, р = 8?е+ 5, р = 82+ 7, отдельно. Чему при этом равна матрица сд? Вам не нужно находить множители: требуется найти только их количество,) 13. [М28] Продолжая предыдущее упражнение, найдите точные формулы для множителей полинома х + 1 по модулю р длн всех нечетных простых чисел р с использованием величии э/-1, ие2, ие — 2, если такие квадратные корни существуют по модулю р.
14. [М28] (Г. Зассенхауз (Н. ХэввепЬаив).) Пусть и(х) — решение (8) и пусть ю(х) П(х — ь), где произведение беретгя по всем 0 < в ( р, таким, что 8сд(и(х), о(х) — в) ф 1. Объясните, как вычислить ю(х) по данным и(х) и о(х). [Укаэакие. Иэ формулы (14) вытекает, что ю(х) является полиномоле минимальной степени, таким, что и(х) делит и~(о(х)).] Р 15. [М27] (Квадратике корки по модулю простого числа.) Разработайте алгоритм для вычисления квадратного корня целого числа и по модулю простого числа р, т. е. найдите число о, такое, что о~ = и шое) р, если оно существует.
Ваш алгоритм должен быть эффективен даже при очень больших целых числах р. (Для р ?4 2 решение этой задачи сводится к 1 гшению квадратного уравнения по модулю р с использованием обычной квадратичной фе |~мулы.) Указание. Рассмотрите, что произойдет после применения методов разложения из этого раздела к папиному х — и. 2 16. [МЯ0] (Конечные колл.) Назначение дашюго упражнения — доказать основные свойства полей, введенных Э. Галуа (Е. Оа1о1в) в 1830 году. а) Дано, что 7(х) — неприводимый по модулю простого числа р полинам степени и. Докажите, что р" полиномов гтепени, меныоей п, образуют поле с арифметикой по модулю г(х) и р, [Указание, Существование неприводимых полиномов любой степени доказано в упр.
4, поэтому паля с р" элементами существуют для всех простых чисел р и всех и > 1.] Ь) Покажите, что любое поле с р" элементами имеет элемент "примитивный корень" б, тш кой, что элементами поля являются (О, 1,б,б~,...,Ег"-г). [Указание. В упр. 3.2.1.2 — 16 содержится доказательство для частного случая и = 1.] с) Если у(х) — неприводимый полинам по модулю р степени н, докажите, что хг — х делится на г(х) тогда и только тогда, когда т кратно и. (Отскгда следует, что можно быстро проверить неприводимость.
Данный полинам н-й степени 1(х) неприводим по модулю р тогда и только тогда, когда хг" — х делится на с(х) и хс" ' — х .! !"(х) для всех простых д, которые делят гь) 12. [МЗЗ] Пусть Š— поле с 13 элементами. Сколько элементов Е имеют порядок ! для каждого целого 1 < !' < 13г? ( орядком элемевта а является наименьшее положительное целое число т, такое, что а = 1.) и 18. [Мху] Пусть и(х) = и х" + +ие, и„ф 0 является примитивным полиномом с целыми коэффициентами и пусть и(х) — нормированный полипом, определяемый как о(х) = и„"~ и(х(и„) = х" + и -гх" ~ + и„-ги„х" г + '+ иеии (а) Дано, что о(х) имеет полное разложение рг(х)...
р,(х) над кольцом целых чисел, где каждый рг(х) нормирован. Каково полное разложение паеинома и(х) над кольцом целых чиселт (Ь) Если ш(х) = х™+ ш гх~ '+ + ше является множителем о(х), докажите, что шг является множителем и~ при 0 < ?с < т. 19. [МЯО] (Критерий Эйзеншглейна,) Возможно, самый известный класс неприводимых полиномов над кольцом целых чисел был введен Т. Шенеманном (Т. БсЬопепзавп) в Сге!!е 32 (1846), 100, а популяризован Г. Эйзенштейном (С. ЕЫепшеш) в Сге!!е 39 (1850), 166-169. Пусть р является простым числом и пусть полипом и(х) = и„х" +.
+ ие имеет следующие свойства: (1) и„не делится на р; (!!) и„м ..,, ие делятся на р; (ш) ие не делится на рг. Покажите, что и(х) неприводим нэд кольцом целых чисел 20. [НМЗЗ] Если и(х) = и,х" + + ие является некоторым полиномом нед полем комплексных чисел, обозначим []и][ = (]и„]г + + ]ие[ ) а) Пусть и(х) = (х — а)ш(х) и о(х) = (бх — 1)ш(х), где а — произвольное комплексное число, а б — сопряженное ему. Докажите, что ]]и]] = ]]о]].
Ь) Пусть иь(х — а1)... (х — ае) представляет собой полное разложение и(х) над полем комплексных чисел, Введем обозначение М(и) = [и„[]["., шах(1,]ог]). Докажите, что М(и) < [(и]]. с) Покажите, что ]иг] < (ьу )М(и) + (.,)]и„] длЯ 0 < З < и. 6) Объедините эти результаты для доказательства того, что если и(х) = о(х)ш(х) и е(х) = о ~х + + оа, где и, о, ш имеют целые коэффициенты, то коэффициенты о ограничены следующим образом: [о,] < ('" ')]]и]] + (,, )[и„[.
21. [НМЗ8] Продолжая упр. 20, выведем полезные границы коэффициентов полиномов асл многих переменных над кольцом целых чисел. Для удобгтва будем использовать полужирные символы, чтобы обозначить последовательности из г целых чисел. Таким образом, вместо записи и(хп...,хс) = ~г ид,, „х, ...
х, д л й й можно записать просто и(х) = 2,. изх". Обратите внимание на обозначение х"; также обозначаем )! = уг'...д' и Е) = ?г+ . +уь а) Докажите тождество 1 ФЧ' г! в! — ~ [р — )=г? — ЦарЬ . ) [г — ) =в — Цс,0, ))(с! ' ч(р — ))! (г — ))~ зж ' 'юч>о , >о Ь ~ [Р+в=[]ар4, ~ [г1+г=)]Ьчс,. ~>о рэ>о ч,г>о Полинам и(х) = 2 „. изхз называется однородным полиномом степени и, если каждый член имеет общую степень и. Таким образом, Е) = и при из ф О.
Рассьготрил~ взвешенную сумму коэффициентов В(и) = 2,'1)! [из[~. Используя п. (а), покажите, что В(и) > В(о)В(гг), если и(х) = о(х)и~(х) однороден. Варма Бомбьери [и] полинома и(х) определяется квк;/В(и)/п.', если и — однородный полинам степени и. Она определена также для неоднородных полиномов посредством добавления вовой переменной хьгг и умножения каждого члена на степень хгэц такую, что и становится однородным без увеличения его максимальной степени.
Например, пусть и(х) = 4х + х — 2, соответствующий однородный полинам — 4х + хд — 20 и з 3 2 Э [и]~ = (3!О!4 +1 2 1 +О! 3! 2 )/3! = 16+ э+4. Если и(х 0 х) = Зхр~ — хэ, аналогично получаем [и]' = (1! 3! 0'О! 3 +О! 0' 2! 2! 1 )/4! = э+-'. Что говорит п. (Ь) о связи между [и], [о] и [ю] при и(х) = и(х)ге(х)? Докажите, что если и(х) — приводимый полинам степени п от одной переменной, то он имеет множитель, коэффициенты которого не превышают арг [и]ы /(и/4)! по абсолютному значению. Чему равно соответствующее значение для однородных полиномов от Г переменных? Вычислите [и] явно и вснмптотически при и(х) = (х~ — 1)".
Докажите, что [и][и] > [ии]. Покажите, что 2 О~ЛХ(и) < [и] < 2"г~ЛХ(и), если и(х) — полинам степени и и Лу(и)— величина, определенная в упр. 20. (Вследствие этого грань в п. (д) примерно раева квадратному корню грани, полученной в упр. 20.) [М24) (Лемма Хеьселл.) Пусть и(х), о,(х), 1г,(х), а(х), Ь(х) представляют собой номы с целымн коэффициентами, удовлетворяющими соотношениям Ь) с) е) 1) 3) ь 22. поли и(г)— : о,(х)иь(х) шойр', а(х)е,(х) + Ь(х)ю,(х) эз 1 шобр, где р — простое число, е > 1, о,(х) — нормированный полинам, г)ей(а) < г(ей(ю,), бей(Ь) < дей(и,) и г)ей(и) = дей(о.) -1- бей(иь). Покажите, как вычислить полиномы ог ы (х) = г,(х) и иьэ.~(х) ю ии(х) (по модулю р'), удовлетворяющие тем же условиям с е, увеличенным на 1.
Кроме того, докажите, что о,ьг(х) и ш, г(х) единственны по модулю р'+'. Используйте свой метод для р = 2 для доказательства того, что (22) неприводим над кольцом целых чисел, начиная с его разложения по модулю 2, найденного в упр. 10. (Заметьте, что расширенный алгоритм Евклида из упр. 4.6.1 — 3 даст процесс, начинающийся с е = 1.) 23.
[ВМ23] Пусть и(х) является полиномом с целыми коэффициентами, свободным от квадратов Докажите, что вмеется только конечное число простых чисел р, таких, что этот полинам и(х) не является свободным от квадратов по модулю р. 24. [М20] В тексте раздела говорится о разложении над кольцом целых чисел, в не над полем рациональных чисел. Обьясните, как найти полное разложение полннома с рациональными коэффициентами над полем рациональных чисел. 25.
[М35] Каково полное разложение полинома х~+х" +к~+к+2 над полем рациональных чисел? 26. [80] Пусть с)с, ..., с1, — степени неприводимых множителей полинома и(х) по модулю р с правильной кратностью, так что с1с + + с1„= и = с1еб(в). Объясните, как найти множество (Йей(а) ] и(х) св а(х)ш(х) пшс1 р для некоторых а(х), ис(х)), выполнив 0(г) операций над битовой строкой длины и. 2 с. [НМУО] Докажите, что случайный примитивный полинам над кольцом целых чисел в некотором определенном смысле "почти всегда" неприводим. 28.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
