Упражнения

Раздел 6.1.1

1. Пользуясь методом Шуберта-Кронекера, разложите на множители следующие полиномы:

Раздел 6.2.1

1. Рассмотрим полином Свободен ли он от квадратов в

(Указание. Для ответа на эту часть упражнения посмотрите шаг 2 разд. 6.1.2, т.е. выполните вычисление ) Используйте алгоритм PSQFFF для нахождения свободных от квадратов сомножителей полинома

2. Рассмотрим полином Свободен ли он от квадратов в ? Используйте алгоритм PSQFFF для нахождения свободных от квадратов сомножителей полинома .

Раздел 6.2.2

1. Докажиту теорему 6.2.7 в обратном направлении, т.е. докажите, что если функция F определена на натуральных числах, а функция определена равенством

2. Вычислите и найдите все неприводимые полиномы степени 4 в

Раздел 6.2.3

1. Докажите лемму 6.2.11.

2. Используя методы, приведенные в этом разделе, разложите на множители полиномы

Раздел 6.2.4

1. Покажите, что если — взаимно простые полиномы в кольце (или над произвольным полем) и принадлежит то

2. Докажите, что если V — векторное пространство размерности над полем то оно содержит элементов.

3. Пользуясь алгоритмом Берлекэмпа, разложите на множители полиномы

Раздел 6.3

1. Найдите границы для коэффициентов сомножителей в полиномов

Раздел 6.3.1

1. Рассмотрим полиномы

В упражнениях разд. 6.2.4 мы просили разложить некоторые из этих полиномов на множители в для выделенных значений кроме того, в упражнениях разд. 6.3 мы просили вычислить соответствующие границы для коэффициентов их сомножителей в Возьмите полином по своему выбору и выполните линейный подъем его разложения по модулю до разложения над целыми числами.

2. Какова функция времени вычисления для алгоритма HLLA?

3. Опишите основные шаги алгоритма HQLA (Hensel’s Quad-ratic-Lifting Algorithm).

В следующих упражнениях мы применяем понятие подзема к решению полиномиального сравнения

4. Докажите, что произведение любых к последовательных целых чисел делится на (Указание. Воспользуйтесь тем, что» согласно формуле бинома, коэффициент при в разложении бинома является целым числом )

5. С помощью упр. 3 докажите, что если — решение сравнения то решение по модулю получается из линейного сравнения

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

Упр. 5 используется в следующих упражнениях.

6. Решите сравнение

7. Решите сравнение

8. Решите сравнение

9. (Подъем квадратного корня.) Пусть — нечетное целое число, и предположим, что и a — квадрат некоторого целого числа по модулю . Мы хотим найти такой, что , в предположении, что для каждого i нам известен невычет по модулю (см. также упр. 22 и 23 разд. 3.3.1).

a. Для каждых фиксированных а воспользуйтесь алгоритмом упр. 23 к разд. 3.3.1, чтобы определить некоторое такое, что ). Вычислив такое найдите некоторое такое, что

b. Опишите, как найти такой, что

Раздел 6.3.2

1. Можно ли разложить на множители полином над целыми числами?

2. Разложите на множители полиномы над целыми числами.

Упражнения по программированию

Раздел 6.3.1

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