Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

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

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

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

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

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

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

Сбоев А.В.

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

Ярославль, 2003

Содержание

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

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

   1. Алгоритм вычисления a^d mod m

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

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

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

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

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

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

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

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

      1. Схема Горнера

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

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

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

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

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

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

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

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

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

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

1. Представим d в двоичной системе счисления d = d₀2^r+…+d_r-12+d_r, где d_i, цифры в двоичном представлении, равны 0 или 1, d₀ = 1.

2. Положим a₀ = a и затем для i = 1,…,r вычислим a_i  a²_i-1a^di (mod m).

3. a_r есть искомый вычет a^dmod m.

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

a_i  a²_i-1a^{d02^i+…+di} (mod m),

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

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

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

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

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

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

n₀ = b_t2^t + b_{t – 1}2^{t – 1} + … + b₁2¹ + b₀2⁰,

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

или же .

Е сли задана последовательность (x_i)_{0  i  t}, первый элемент которой есть x₀ и x_i для i [1,t] определено соотношением x_i = x_{i – 1}², то можно записать = {x_i | 0  i  t, b_i  0}. Чтобы завершить построение алгоритма и иметь возможность получить значение предыдущего произведения, необходимо вычислить биты b_i числа n₀. Для последовательности (n_i) _{0  i  t+1} (с начальным элементом n₀), определённой соотношением n_i = [n_i–1/2] для любого i  [1, t + 1], бит b_i равен нулю, если n_i чётно, и равен единице в противном случае. Первое значение индекса i, для которого n_i равно нулю, есть t + 1.

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

2^t  n  2^{t + 1} или t  log₂n < t + 1.

Первая часть этого свойства может быть выражена следующим образом: [n/2^{t + 1}] = 0 и [n/2^t]  0, что позволяет точно определить число совершаемых делений n, равное числу итераций алгоритма при заданном значении n. Очевидно, нужно совершить t + 1 итераций, чтобы выполнить алгоритм, т. е. [log₂n] + 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.

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

r₁ = b,…, 0  r_i+1 < r_i, i = 0,1,…,n - 1.

Пусть также u₀ = 1, u₁ = 1, u_k+1 = u_k+u_k-1, k  1, - последовательность Фибоначчи. Индукцией по i от i = n - 1 до i = 0 легко доказывается неравенство r_i+1  u_n-i. А так как u_n  10^(n-1)/5, то имеем неравенства 10^p > b = r₁  u_n  10^(n-1)/5 и n < 5p+1.

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

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

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

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

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

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

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

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

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

Для некоторых задач эффективные алгоритмы вообще не известны. Иногда в таких случаях всё же можно предложить последовательность действий, которая, «если повезёт», быстро приводит к требуемому результату. Существует класс так называемых вероятностных алгоритмов, которые дают правильный результат, но имеют вероятностную оценку времени работы. Обычно работа этих алгоритмов зависит от одного или нескольких параметров. В худшем случае они работают достаточно долго. Но удачный выбор параметра определяет быстрое завершение работы. Такие алгоритмы, если множество «хороших» значений параметров велико, на практике работают достаточно эффективно, хотя и не имеют хороших оценок сложности.

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

Рассмотрим вероятностный алгоритм, позволяющий эффективно находить решения полиномиальных сравнений по простому модулю. Пусть p – простое число, которое предполагается большим, и f(x)Z[x] – многочлен, степень которого предполагается ограниченной. Задача состоит в отыскании решений сравнения

f(x)  0 (mod p). (1)

Например, речь может идти о решении квадратичных сравнений, если степень многочлена f(x) равна 2. Другими словами, мы должны отыскать в поле F_p = Z/pZ все элементы, удовлетворяющие уравнению f(x) = 0.

Согласно малой теореме Ферма, все элементы поля F_p являются однократными корнями многочлена x^p - x. Поэтому, вычислив наибольший общий делитель d(x) = (x^p - x, f(x)), мы найдём многочлен d(x), множество корней которого в поле F_p совпадает с множеством корней многочлена f(x), причём все эти корни однократны. Если окажется, что многочлен d(x) имеет нулевую степень, т. е. лежит в поле F_p, это будет означать, что сравнение (1) не имеет решений.

Для вычисления многочлена d(x) удобно сначала вычислить многочлен c(x)x^p (mod f(x)), пользуясь алгоритмом, подобным описанному выше алгоритму возведения в степень (напомним, что число p предполагается большим). А затем с помощью аналога алгоритма Евклида вычислить d(x) = (c(x) – x, f(x)). Всё это выполняется за полиномиальное количество арифметических операций.

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов реферата