Быстрые вычисления с целыми числами и полиномами

Министерство образования Российской Федерации

Ярославский Государственный Университет им. П.Г. Демидова

Курсовая работа

По дисциплине «Алгебра»

Быстрые вычисления с целыми числами и полиномами

Выполнил: Студент группы КБ-11

Сбоев А.В.

Проверил: Дурнев В.Г.

Ярославль, 2003

Содержание

1. Введение. Сложность теоретико-числовых алгоритмов.

2. Полиномиальные алгоритмы

2.1 Алгоритм вычисления ad mod m

2.2 Дихотомический алгоритм возведения в степень

2.3 Алгоритм Евклида

2.4 Алгоритм решения уравнения ax + by = 1

3. Полиномиальная арифметика

3.1 Алгоритм нахождения делителей многочлена f(x) в кольце Fp[x]

3.2 Произведение и возведение в степень многочленов, заданных массивами

3.3 Небольшие оптимизации для произведения многочленов

3.4 Вычисление полиномов

3.4.1 Схема Горнера

3.4.2 Интерполяционная формула Ньютона и табулирование значений многочлена

4. Дискретное логарифмирование

1. Введение. Сложность теоретико-числовых алгоритмов

Сложность алгоритмов теории чисел обычно принято измерять количеством арифметических операций (сложений, вычитаний, умножений и делений с ос-татком), необходимых для выполнения всех действий, предписанных алгорит-мом. Впрочем, это определение не учитывает величины чисел, участвующих в вычислениях. Ясно, что перемножить два стозначных числа значительно слож-нее, чем два однозначных, хотя при этом и в том, и в другом случае выполняет-ся лишь одна арифметическая операция. Поэтому иногда учитывают ещё и ве-личину чисел, сводя дело к так называемым побитовым операциям, т. е. Оцени-вая количество необходимых операций с цифрами 0 и 1, в двоичной записи чи-сел. Это зависит от рассматриваемой задачи, целей автора и т. д.

На первый взгляд странным также кажется, что операции умножения и де-ления приравниваются по сложности к операциям сложения и вычитания. Жи-тейский опыт подсказывает, что умножать числа значительно сложнее, чем складывать их. В действительности же, вычисления можно организовать так, что на умножение или деление больших чисел понадобится не намного меньше битовых операций, чем на сложение. Существует алгоритм Шенхаге – Штрас-сена, основанный на так называемом быстром преобразовании Фурье, и тре-бующий O(n ln n lnln n) битовых операций для умножения двух n-разрядных двоичных чисел. Таким же количеством битовых операций можно обойтись при выполнении деления с остатком двух двоичных чисел, записываемых не более чем n цифрами. Для сравнения отметим, что сложение n-разрядных дво-ичных чисел требует O(n) битовых операций.

Говоря о сложности алгоритмов, мы будем иметь в виду количество ариф-метических операций. При построении эффективных алгоритмов и обсуждении верхних оценок сложности обычно хватает интуитивных понятий той области математики, которой принадлежит алгоритм. Формализация же этих понятий требуется лишь тогда, когда речь идёт об отсутствии алгоритма или доказа-тельстве нижних оценок сложности.

2. Полиномиальные алгоритмы

Четыре приведённых ниже алгоритма относятся к разряду так называемых полиномиальных алгоритмов. Это название носят алгоритмы, сложность кото-рых оценивается сверху степенным образом в зависимости от длины записи входящих чисел. Если наибольшее из чисел, подаваемых на вход алгоритма, не превосходит m, то сложность алгоритмов этого типа оценивается величиной O(lncm), где c – некоторая абсолютная постоянная. Во всех приведённых при-мерах с =1.

Следующий алгоритм вычисляет admod m. При этом, конечно, предполага-ется, что натуральные числа a и d не превосходят по величине m.

2.1 Алгоритм вычисления ad mod m

1. Представим d в двоичной системе счисления d = d02r+…+dr-12+dr, где di, цифры в двоичном представлении, равны 0 или 1, d0 = 1.

2. Положим a0 = a и затем для i = 1,…,r вычислим ai  a2i-1adi (mod m).

3. ar есть искомый вычет admod m.

Справедливость этого алгоритма вытекает из сравнения

ai  a2i-1ad02^i+…+di (mod m),

легко доказываемого индукцией по i.

Так как каждое вычисление на шаге 2 требует не более трёх умножений по модулю m и этот шаг выполняется r  log2 m раз, то сложность алгоритма может быть оценена величиной O(ln m).

2.2 Дихотомический алгоритм возведения в степень.

В общем виде дихотомический алгоритм позволяет вычислить n–ю степень в моноиде. Будучи применён к множеству целых чисел с операцией сложения, этот метод позволяет умножать два целых числа и более известен как египет-ское умножение.

Классический алгоритм возведения в степень посредством последователь-ного умножения характерен, главным образом, своей неэффективностью в обычных обстоятельствах – его время работы линейным образом зависит от по-казателя степени.

Возьмём моноид М с операцией умножения и рассмотрим некоторый эле-мент x0 из М, а также произвольное натуральное число n0. Для того, чтобы вы-числить , представим n0 в двоичной системе счисления:

n0 = bt2t + bt – 12t – 1 + … + b121 + b020,

предполагая, что n0 содержит (t + 1)двоичных цифр (т. е. что bt  0 и bt + 1 = 0). В этих условиях вычисляемое выражение может быть записано:

или же .

Если задана последовательность (xi)0  i  t, первый элемент которой есть x0 и xi для i [1,t] определено соотношением xi = xi – 12, то можно записать = {xi | 0  i  t, bi  0}. Чтобы завершить построение алгоритма и иметь возмож-ность получить значение предыдущего произведения, необходимо вычислить биты bi числа n0. Для последовательности (ni) 0  i  t+1 (с начальным элементом n0), определённой соотношением ni = [ni–1/2] для любого i  [1, t + 1], бит bi ра-вен нулю, если ni чётно, и равен единице в противном случае. Первое значение индекса i, для которого ni равно нулю, есть t + 1.

Ясно, что число итераций, необходимых для выполнения алгоритма, зави-сит только от показателя n.

2t  n  2t + 1 или t  log2n < t + 1.

Первая часть этого свойства может быть выражена следующим образом: [n/2t + 1] = 0 и [n/2t]  0, что позволяет точно определить число совершаемых де-лений n, равное числу итераций алгоритма при заданном значении n. Очевидно, нужно совершить t + 1 итераций, чтобы выполнить алгоритм, т. е. [log2n] + 1 итераций. Следовательно, трудоёмкость алгоритма есть O(log n).

Третий алгоритм – это классический алгоритм Евклида вычисления наи-большего общего делителя целых чисел. Мы предполагаем заданными два на-туральных числа a и b и вычисляем их наибольший общий делитель (a,b).

2.3 Алгоритм Евклида

1. Вычислим r – остаток от деления числа a на b, a = bq+r, 0  r < b.

2. Если r = 0, то b есть искомое число.

3. Если r  0, то заменим пару чисел (a,b) парой (b,r) и перейдём к шагу1.

Не останавливаясь на объяснении, почему алгоритм действительно находит (a,b), докажем некоторую оценку его сложности.

Теорема 1. При вычислении наибольшего общего делителя (a,b) с помощью алгоритма Евклида будет выполнено не более 5p операций деления с остат-ком, где p есть количество цифр в десятичной записи меньшего из чисел a и b.

Доказательство. Положим r0 = a > b и определим r1,r2,…,rn - последова-тельность делителей, появляющихся в процессе выполнения шага 1 алгоритма Евклида. Тогда

r1 = b,…, 0  ri+1 < ri, i = 0,1,…,n - 1.

Пусть также u0 = 1, u1 = 1, uk+1 = uk+uk-1, k  1, - последовательность Фибоначчи. Индукцией по i от i = n - 1 до i = 0 легко доказывается неравенство ri+1  un-i. А так как un  10(n-1)/5, то имеем неравенства 10p > b = r1  un  10(n-1)/5 и n < 5p+1.

Немного подправив алгоритм Евклида, можно достаточно быстро решать сравнения ax  1 (mod m) при условии, что (a,b) = 1. Эта задача равносильна поиску целых решений уравнения ax + by = 1.

2.4 Алгоритм решения уравнения ax + by = 1

0. Определим матрицу E =

1. Вычислим r – остаток от деления числа a на b, a = bq + r, 0  r < b.

2. Если r = 0, то второй столбец матрицы Е даёт вектор (x y) решений урав-нения.

3. Если r  0, то заменим матрицу Е матрицей

4. Заменим пару чисел (a,b) парой (b,r) и перейдём к шагу 1.

Если обозначить через Еk матрицу Е, возникающую в процессе работы ал-горитма перед шагом 2 после k делений с остатком (шаг 1), то в обозначениях из доказательства теоремы 1 в этот момент выполняется векторное равенство (a,b)Ek = (rk-1,rk). Его легко доказать индукцией по k. Поскольку числа a и b взаимно просты, имеем rn = 1, и это доказывает, что алгоритм действительно даёт решение уравнения ax + by = 1. Буквой n мы обозначили количество деле-ний с остатком, которое в точности такое же, как и в алгоритме Евклида.

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

Для некоторых задач эффективные алгоритмы вообще не известны. Иногда в таких случаях всё же можно предложить последовательность действий, кото-рая, «если повезёт», быстро приводит к требуемому