НАУЧНАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Быстрые вычисления с целыми числами и полиномами

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

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

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

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

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

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

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

Сбоев А.В.

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

Ярославль, 2003

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

многочлена

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

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

Сложность алгоритмов теории чисел обычно принято измерять количеством

арифметических операций (сложений, вычитаний, умножений и делений с

остатком), необходимых для выполнения всех действий, предписанных

алгоритмом. Впрочем, это определение не учитывает величины чисел,

участвующих в вычислениях. Ясно, что перемножить два стозначных числа

значительно сложнее, чем два однозначных, хотя при этом и в том, и в другом

случае выполняется лишь одна арифметическая операция. Поэтому иногда

учитывают ещё и величину чисел, сводя дело к так называемым побитовым

операциям, т. е. Оценивая количество необходимых операций с цифрами 0 и 1,

в двоичной записи чисел. Это зависит от рассматриваемой задачи, целей

автора и т. д.

На первый взгляд странным также кажется, что операции умножения и

деления приравниваются по сложности к операциям сложения и вычитания.

Житейский опыт подсказывает, что умножать числа значительно сложнее, чем

складывать их. В действител