Упражнения

Раздел 3.1.1

1. Если мы работаем в полиномиальной арифметике по модулю 7, то чему равно минус Чему равно произведение этих полиномов?

2. Является ли произведение нормированных полиномов нормированным? Чему равна степень произведения полиномов степеней тип соответственно? Чему равна степень суммы полиномов степеней тип соответственно?

3. Для каких простых чисел существуют, и существуют ли вообще, такие числа, что полиномы совпадают как функции на

Найдите корни полинома

b. Используя PDF, разделите на

5. Покажите, что если — два полинома в и полином нормирован, то при выполнении деления в кольце полиномы принадлежат кольцу Что произойдет, если полином не нормирован?

6. Пусть — два полинома над полем вещественных чисел степени не более . Если — различные числа, примем то для всех значений

7. Пусть — полином над полем вещественных чисел степени , и пусть вещественное число, такое, что Если удовлетворяет соотношениям

то ни один вещественный нуль полинома не превосходит

В двух следующих упражнениях представлены два специальных типа полиномов. Они использовались для тестирования различных методов отделения вещественных корней, описанных в гл. 7.

8. Полиномы Чебышева могут быть рекурсивно получены по формулам

Все корни этих полиномов простые, вещественные, расположены в открытом интервале и симметричны (т.е. если — корень, то и также корень); см. также разд. 7.6. Определите

9. Полиномы Лежандра могут быть рекурсивно получены по формулам

Все корни этих полиномов простые, вещественные, расположены в открытом интервале и симметричны (т.е. если — корень, то и — также корень). Определите с целыми коэффициентами.

Раздел 3.1.2

1. Для полинома найдите оценку для времени вычисления полинома . [Указание. См. также статью (Akritas, Danielopoulos, 1980).]

2. Для вычислите используя схему, о которой говорилось в этом разделе.

3. Чему равно время вычислений подхода «грубой силы» для вычисления значения полинома в данной точке? А именно, каждый член вычисляется по формуле а затем умножается на

Следующие упражнения распространяют метод Руффини-Горнера на полиномы с комплексными коэффициентами.

4. Рассмотрим полином где теперь (т.е. коэффициенты являются гауссовыми числами, определенными в упр. 7 разд. 2.2.2) и (гауссов полином). Следовательно, в рекурсивной схеме (RH) этого раздела будет комплексным и вида (Напомним, Что )

Покажите, что следующая рекурсивная схема — это метод Руффини-Горнера для полиномов над полем комплексных чисел:

и для

5. Вычислите значение полинома в точке

6. Вычислите значение полинома в точке

7. Разработайте алгоритм, который для данного гауссова полинома и гауссова целого числа а вычисляет полином

8. Воспользуйтесь алгоритмом упр. 7 и вычислите где — полином из упр. 5.

9. Воспользуйтесь алгоритмом упр. 7 и вычислите где — полином из упр. 6.

Раздел 3.1.3

1. Каково время вычисления интерполяционного полинома Лагранжа?

2. Используйте интерполяцию Лагранжа для нахождения полинома степени не более 2, такого, что

3. Найдите полином , такой, что

4. Покажите, что

5. Пусть — различные элементы поля J, и пусть принадлежат J. Пусть — полином из , такой, что Покажите, что для некоторого полинома из такого, что Чему равны значения полинома в точках Опишите рекурсивную процедуру вычисления Используйте эту процедуру, чтобы выполнить интерполяцгао в упр. 1 и 2.

6. (Двумерная интерполяция.) Разработайте алгоритм для вычисления полинома — поле, где степень полинома по у меньше

для различных Покажите, что полином определен однозначно.

a. Если предположить, что операции в поле J выполняются за время и что степени полиномов меньше , чему равно время вычислений вашего алгоритма (в терминах )?

b. Вычислите полином , такой, что

7. (Многомерная интерполяция.) Разработайте алгоритм для вычисления полинома поле, где степень полинома по меньше

для различных Покажите, что полином определен однозначно. Более того, предполагал, что операции в поле J выполняются за время что степени полиномов меньше оцените время вычислений вашего алгоритма.

Раздел 3.1.4

1. Покажите, что тогда и только тогда, когда определяет отношение эквивалентности на — поле.

2. Завершите доказательство теоремы 3.1.9.

3. Используя схему -интерполяция», разработайте алгоритм для пробного деления двух полиномов над полем, т.е. то возвращают частное, в противном случае утверждается, что не делит [Указание. Здесь существенно то, что если , то для частного мы имеем Таким образом, если степень полинома, полученного интерполяцией, не равна , то мы можем утверждать, что не делит

4. а. Чему равно время вычислений алгоритма, разработанного в упр. 3?

b. Покажите, как полученный алгоритм вычисляет пробные деления над для

5. Разработайте алгоритм, аналогичный алгоритму упр. 3 для пробного деления над Z, разделив 969/19 и 970/19, пользуясь делениями только над для .

6. Чему равно время вычислений алгоритма «(вычисление значений)-интерполяция» для полиномиального умножения над разработанного в этом разделе? (Как всегда, предполагается единичная цена операций одинарной точности.)

Раздел 3.2.1

1. Делит ли полином полином над целыми числами?

2. Найдите все такие, что делит

3. Вычислите наибольший общий делитель полиномов над вещественными числами.

4. В упр. 7 разд. 2.2.2 мы определили кольцо гауссовых целых чисел; напомним, что если — такое число, , то его норма равна Покажите, что — евклидова область.

Раздел 3.2.2

1. (Цепные дроби для полиномиальной аппроксимации.) Пусть — два полинома над полем, причем и пусть — полиномы, получающиеся как частные при применении алгоритма Евклида к кроме того, пусть Мы хотим показать, что подходящие дроби для цепной дроби суть «лучшие» приближения низких степеней для рациональной функции где подходящие дроби определяются аналогично тому, как они определялись в разд. 2.2.4. (Читателю следует еще раз посмотреть его.)

Докажите, что если — два полинома, таких, что для некоторого , то для некоторой константы с. Каждый — «лучший» полином в том смысле, что ни для какого ненулевого полинома меньшей степени нельзя подобрать полином так, чтобы степень полинома не превосходила степени [Указание. Воспользуйтесь алгоритмом ХЕА-Р; см. также (Knuth, 1981; р. 622).]

2. Докажите, что если — поле, , то

3. Докажите, что если — поле, , то

4. а. Примените алгоритм ХЕА-Р к полиномам

b. Решите в уравнение

с. В найдите полиномов [Указание. Воспользуйтесь тождеством

5. Используйте чтобы найти для в каждом из следующих примеров. В каждом случае вычислите соответствующие полиномы такие, что

Раздел 3.2.3

1. Докажите, что в нет неприводимых полиномов нечетной степени и что в нет неприводимых полиномов степени 2.

2. Известно, что у полинома есть корни —i и разложите в произведение неприводимых полиномов в

3. Найдите, если они существуют, все сомножители степени 1 в следующих полиномов:

4. Докажите, что если полином нормирован, то он примитивен.

5. Покажите, что если число таково, что полиномы оба примитивны, то

6. Является ли полином неприводимым в

7. Покажите, что если — простое число, то полином неприводим в

8. Определите, какие из следующих полиномов неприводимы в

Раздел 3.2.4

1. Примените алгоритм PSQFF для вычисления разложения полинома на свободные от квадратов множители. [Указание. Данный полином — произведение полиномов

2. Вычислите разложение на свободные от квадратов множители следующих полиномов:

(Явная демонстрация различия между разложением на неприводимые множители и разложением на свободные от квадратов множители).

3. Для каждого простого найдите отличный от константы полином над такой, что

4. Докажите, что если — полином из где F — поле, содержащееся в поле комплексных чисел, то не имеет кратных множителей тогда и только тогда, когда

5. Исследуйте следующие полиномы на кратные сомножители в

6. Докажите, что полином имеет кратный сомножитель в тогда и только тогда, когда имеет кратный сомножитель в

Раздел 3.3.1

1. Каковы порядки ненулевых элементов поля

2. Докажите теорему 3.3.9.

3. Пусть — простое число; покажите, что делит тогда и только тогда, когда делит п.

4. Покажите, что если а то где

5. Пусть найдите примитивный корень поля Найдите также минимальный полином элемента

6. Докажите теорему 3.3.16.

7. Найдите все неприводимые сомножители полинома

8. Теорема 3.3.8 утверждает, что у каждого конечного поля есть образующая. Покажите, что если а — образующая поля то также является образующей тогда и только тогда, когда . В частности, имеется всего () различных образующих поля

9. Как мы видели непосредственно перед теоремой 3.3.9, нахождение образующей в конечном поле сильно зависит от разложения числа Покажите, что существует последовательность простых чисел , таких, что вероятность того, что случайный ненулевой элемент а является образующим, стремится к нулю. (Указание. Воспользуйтесь следующими фактами: (а) теоремой Дирихле о простых числах в арифметической прогрессии, которая утверждает, что если пик взаимно просты, то существует бесконечно много простых чисел, которые предыдущим упр. 8, откуда мы делаем вывод, что отношение числа всех ненулевых элементов, являющихся образующими, к числу ненулевых элементов равно где произведение берется по всем стремится к бесконечности, когда произведение берется по всем простым числам.)

10. Используйте теорему 3.3.21, чтобы доказать, что если г — простое число, то существует различных нормированных неприводимых полиномов степени . (Более общий результат получен в разд. 6.2.2.) Заметим, что по малой теореме Ферма — целое число.

11. Предположим, что — степень простого числа Найдите простую формулу для числа нормированных неприводимых полиномов степени над

12. Докажите, что сравнение степени нормирован) имеет решений тогда и только тогда, когда является делителем полинома т.е. тогда и только тогда, когда

где полиномы с целыми коэффициентами и либо полином степени либо нулевой полином.

13. Для и 13 найдите наименьшее положительное целое число, которое порождает ненулевые элементы поля и определите, сколько из чисел является образующими.

14. Сколько элементов содержится в наименьшем расширении поля которое содержит все корни полиномов

15. У каких полиномов в производные тождественно равны нулю?

16. Пусть — конечное поле из элементов и а — отображение, переводящее каждый элемент в его степень: Докажите, что является автоморфизмом поля (т.е. а — это взаимно однозначное отображение, сохраняющее сложение и умножение); элементы поля остающиеся неподвижными под действием а, — это в точности элементы простого поля множество элементов, остающихся неподвижными при — это поле где .

17. Докажите, что если а — какой-либо элемент то элементы поля удовлетворяющие тому же нормированному неприводимому полиному с коэффициентами из (называемые также сопряженными), — это элементы где определено выше в упр. 16.

18. При каких условиях на каждый элемент поля кроме 0 и 1, является образующим ненулевых элементов поля При каких условиях каждый элемент, отличный от 0, 1, является либо образующим, либо квадратом образующего?

19. Предположим, что а удовлетворяет полиному , где

Докажите, что также удовлетворяет этому полиному.

b. Докажите, что если , то

Докажите, что если , то

20. Мы хотим ответить на вопрос: сколько корней имеет уравнение над (Эти корни называются также корнями степени из единицы.) Пусть а — образующий (ненулевых элементов) поля Докажите, что а есть

корень степени из единицы тогда и только когда и что число корней степени из единицы равно . В частности, имеет примитивный корень степени из единицы (т.е. элемент , такой, что степени пробегают все корней степени из единицы) тогда и только тогда, когда если примитивный корень степени из единицы в то также примитивный корень степени тогда и только тогда, когда

21. Сколько корней 15-й степени из единицы имеется в поле из элементов?

22. Для всех а, таких, что элемент а называется квадратичным вычетом по модулю , если сравнение имеет решение. Если оно не имеет решения, то а называется квадратичным невычетом. (См. также упр. ) раздела 2.3.2.)

a. Докажите, что квадратичный вычет никогда не может быть образующим группы ненулевых элементов поля

Покажите, что если — простое число Ферма, то любой квадратичный невычет является образующим группы ненулевых элементов поля более того, покажите, является образующим группы ненулевых элементов поля кроме случая образующим для кроме случая

23. (Вычисление квадратных корней по модулю Пусть — нечетное простое число. Рассмотрим сравнение ), про которое мы знаем, что оно имеет решение (см. упр. ) разд. 2.3.2); мы хотим найти такое целое число которое удовлетворяет этому сравнению. Нужно действовать следующим образом. Пусть к — квадратичный невычет, вычисленный нами каким-либо образом. Запишем в виде где s нечетно, и положим и ). Если то и мы видим, что — требуемый квадратный корень. В противном случае достаточно близко подходит к квадратному корню из а и должно быть соответствующим образом подправлено (с помощью корня степени из единицы). Прежде чем осуществить эту подгонку, заметим следующее:

(i) Величина является корнем степени из единицы ), т.е.

(ii) Элемент является примитивным корнем степени из единицы (см. выше упр. 20). Чтобы убедиться в этом, заметим прежде всего, что и — корень степени из единицы ), потому что

(Заметим, что ), поскольку к — невычет.) Теперь, если и не примитивен, должна существовать меньшая степень и (делитель числа ), дающая 1, откуда следует, что элемент и должен быть четной степенью примитивного корня степени из единицы и, таким образом, и должен быть квадратом в Однако это невозможно, так как

поскольку s нечетно, а А: — невычет.

Таким образом остается вычислить подходящую степень такую, что — требуемый корень из а. Для этого напишем где последовательность битов вычисляется следующим образом:

[1] Поскольку — корень степени из единицы , то, если мы возведем его в степень результат будет равен ±1. Если он равен —1, положим , в противном случае положим В любом случае выбрано так, что ).

(Напомним, что

[2] Предположим теперь, что мы вычислили таким образом, что ), и хотим найти . Снова, как в [1], вычисляем , (где мы возводим теперь в степень ), и если результат равен —1, то полагаем , в противном случае полагаем Таким образом мы гарантируем,

что . Наконец, когда мы дойдем до и найдем получим

и мы вычислили квадратный корень из а.

Примените описанную процедуру к сравнению . См. также упр. 9 разд. 6.3.1. (См. статью Adleman L., Manders К., Miller G. On taking roots in finite fields. Proceedings of the 18th Annual Symposium on the Foundations of Computer Science, pp. 175-178, 1977.)

24. (Вычисление дискретных логарифмов в конечных полях.) Напомним, что если G — конечная группа, таковы, что у является степенью элемента b, то дискретный логарифм у по основанию b — это любое целое число обладающее свойством

Если — поле, в котором мы работаем, то следующий алгоритм основан на предположении, что b — образующий ненулевых элементов поля и что все простые сомножители числа маленькие (т.е. число «гладкое»), (См. Odlyzko A.M. Discrete logarithms in finite fields and their cryptographic significance. Advances in Cryptology, Proceedings of Eurocrypt 84, Sprmget-Verlag, pp. 224-314, 1985.)

Наша цель — найти значение такое, что (т.е. . Если — разложение числа на простые сомножители, то достаточно найти для каждого простого числа , делящего мы можем затем применить греко-китайскую теорему об остатках для вычисления

1 [Предварительные Для каждого простого , делящего вычисляем корни степени из единицы для (Заметим, что если b фиксировано, то эти вычисления нужно выполнить только один раз; с помощью нашей таблицы значений мы готовы вычислять дискретный логарифм любого )

2 [Основной шаг вычисления ] Для каждого простого , делящего выполняем следующее.

Пусть

Чтобы получить мы вычисляем являющийся корнем из единицы, поскольку из следует, что (Напомним, что ) Таким образом, мы сравниваем

и полагаем равным тому значению к для которого

Чтобы получить полагаем Поскольку этот новый элемент у является степенью, мы имеем (не забывайте, ЧТО

Снова мы полагаем равным значению для которого Продолжаем аналогичным образом, пока не вычислим все значения для соответствующего .

3 [Греко-китайский ] В этом месте нам известны для каждого простого числа , делящего Применим греко-китайский алгоритм, чтобы получить

Раздел 3.3.2

1. Пусть — восемь элементов поля определенного неприводимым полиномом над Выпишите таблицы сложения и умножения элементов поля

2. Постройте

3. Для каждой степени найдите число неприводимых над полиномов степени d и составьте их список.

4. Для каждой степени найдите число нормированных неприводимых над полиномов степени d и для составьте их список.

5. Для каждого из следующих полей где найдите неприводимый полином с коэффициентами из простого поля, корень а которого примитивен (т.е. порождает ненулевые элементы поля ), и выпишите все степени а как полиномы от а степени