Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
fn+l fn \ = /1 1
/„ fn-i) U о
а) Допустим, что а > 6 > 0 и для нахождения НОД (а, 6) по алгоритму Евклида (в стандартном варианте с неотрицательными остатками) требуется к делений. Показать, что a ^ fk+2-
б) Используя матричное определение для /„, доказать, что
ап - aln 1 + л/5 , 1 - л/5
/„ = —где «=-^—, «=—J-.
в) Используя пункты а) и б), найти верхнюю оценку для к в терминах а. Сравнить с оценкой, получающейся из доказательства предложения 1.2.1.
§ 2. ДЕЛИМОСТЬ И АЛГОРИТМ ЕВКЛИДА
19
11. Цель этой задачи — найти оценку времени, необходимого для вычисления НОД (а, 6) (где а > 6), которая лучше оценки, полученной в предложении I. 2. 1.
а) Показать, что число двоичных операций, требующихся для проведения деления a = gb + г, есть 0((log 6)(1 + log q)).
б) Применяя результат а) к каждому из O(loga) делений вида r,_i = (7, + 1 г,-+ получить временную оценку в виде 0((log 6)(loga)).
12. Рассмотрим многочлены с вещественными коэффициентами (можно рассматривать ту же задачу для многочленов с коэффициентами из произвольного поля). Пусть есть два многочлена fug. Будем говорить, что f\g, если существует такой многочлен ft, что д = fh. Определим НОД (/, д) аналогично тому, как это делалось для целых чисел, а именно, как многочлен наибольшей степени, делящий fug. Многочлен НОД (/, д) определяется не однозначно, так как, умножая его на любую ненулевую константу, можно получить другой многочлен с теми же свойствами. Однако единственности можно добиться, если потребовать, чтобы многочлен НОД был нормированным, т.е. имел старший коэффициент 1. Многочлены fug называются взаимно простыми, если их НОД есть многочлен-константа 1. Постройте процедуру нахождения НОД для многочленов, полностью аналогичную алгоритму Евклида для целых чисел, и примените ее для нахождения а) НОД (х4 + х2 + 1, Xі + 1) и б) НОД (х4 - 4x3 + 6x2 - 4z + 1, x3 - x2 + x - 1). В каждом случае найдите многочлены и(х) и v(x), представляющие НОД в виде u(x)f(x) + v(x)g(x).
13. Из алгебры известно, что многочлен имеет кратный корень тогда и только тогда, когда он имеет общий делитель со своей производной, в этом случае кратные корни многочлена f(x) являются корнями многочлена НОД (/,/'). Найти кратные корни многочлена х4 — 2т3 — х2 + 2х + 1.
14. (Прежде, чем приступить к этому упражнению, вспомните правила действий с комплексными числами. Заметьте, что так как (a + 6г)(а — 6г) есть вещественное число а2 + б2, то можно производить деление по формуле (c + di)/(a + bi) = (с + di)(a — 6г)/(а2 + б2).) Гауссовыми числами называются комплексные числа, у которых действительная и мнимая части суть целые числа. На комплексной плоскости они изображаются вершинами квадратов, которые образуют целочисленную решетку. Если а и ? — гауссовы числа, то говорят, что a\?, если существует такое гауссово число 7, что ? = ay. Определим НОД [ct,?) как максимальное по модулю гауссово число ё, делящее как а, так и ?. (Напомним, что модуль \6\ — это расстояние от точки 8 на комплексной плоскости до точки 0, т.е. квадратный корень из суммы квадратов действительной и мнимой частей). НОД определен не единственным образом, потому что его можно умножить на ±1 или ±г и получить другое 6 с тем же модулем и тоже делящее и а, и ?. Это дает четыре возможности. Мы будем рассматривать любое из этих четырех чисел как НОД.
Заметим, что любое комплексное число может быть записано в виде суммы гауссова числа и комплексного числа, действительная и мнимая части которого заключены в промежутке от —1/2 до 1/2. Показать, что поэтому мы можем разделить одно гауссово число а на другое гауссово число ? и получить частное и остаток в виде гауссовых чисел, причем остаток по модулю будет меньше ?. Используйте этот факт, чтобы сформулировать алгоритм Евклида для получения НОД двух гауссовых чисел. Воспользуйтесь этим алгоритмом для нахождения а) НОД (5 + 6г, 3 — 2І) и б) НОД (7 - 11«, 8 — 9г). В каждом случае представьте НОД в виде линейной комбинации ua + v?, где «ял являются гауссовыми числами.
15. Последняя задача дает эффективный способ представления некоторых больших простых чисел в виде суммы двух квадратов. Например, предположим,
20
ГЛ. I. ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ЧИСЕЛ
что р — простое число, делящее число вида fc6 + 1. Мы хотим записать р в виде р = с2 + d2, где с и d — целые. Это эквивалентно нахождению нетривиального гауссова делителя числа р, так как c2+d2 = (c + di)(c — di). Мы можем действовать следующим образом. Заметим, что
Ь6 + 1 = (б2 + 1)(64 - Ь2 + 1) и б4 -б2 + 1 = (б2 - I)2 +62.
По четвертому свойству делимости простое число р должно делить один из множителей в правой части первого равенства. Если p\(b2 + 1) = (6 + і)(Ь — і), то НОД (р, 6 + 0 дает нам нужное c + di. Если р|(64 -62 + 1) = ((62 - 1) + 6i)((62 - 1) -Ы), то НОД (р, (б2 — 1) + 6г) дает нам с + di.
Пример. Простое число 12277 делит второй сомножитель в произведении 20е + 1 = (2П2 + 1)(204 - 202 + 1). Поэтому найдем НОД (12277, 399 + 20І):
