Министерство образования Российской Федерации
Ярославский Государственный Университет им. П.Г. Демидова
Курсовая работа
По дисциплине «Алгебра»
Быстрые вычисления с целыми числами и полиномами
Выполнил: Студент группы КБ-11
Сбоев А.В.
Проверил: Дурнев В.Г.
Ярославль, 2003Содержание
Введение. Сложность теоретико-числовых алгоритмов.
Полиномиальные алгоритмы
Алгоритм вычисления ad mod m
Дихотомический алгоритм возведения в степень
Алгоритм Евклида
Алгоритм решения уравнения ax + by = 1
Полиномиальная арифметика
Алгоритм нахождения делителей многочлена f(x) в кольце Fp[x]
Произведение и возведение в степень многочленов, заданных массивами
Небольшие оптимизации для произведения многочленов
Вычисление полиномов
Схема Горнера
Интерполяционная формула Ньютона и табулирование значений многочлена
Дискретное логарифмирование
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
Представим d в двоичной системе счисления d = d02r+…+dr-12+dr, где di,
цифры в двоичном представлении, равны 0 или 1, d0 = 1.
Положим a0 = a и затем для i = 1,…,r вычислим ai ( a2i-1adi (mod m).
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 b и определим r1,r2,…,rn –
последовательность делителей, появляющихся в процессе выполнения шага 1
алгоритма Евклида. Тогда
r1 = b,…, 0 ( ri+1 b = r1 ( un ( 10(n-1)/5 и n 2 эта вероятность, конечно, ещё меньше. Более
тонкий анализ с использованием оценок А. Вейля для сумм характеров
показывает, что вероятность для многочлена f(x) не распасться на
множители при однократном проходе шагов алгоритма 1-4 не превосходит 2-n
+ O(p-1/2). Здесь постоянная в O(.) зависит от n. В настоящее время
известно элементарное доказательство оценки А. Вейля.
Если в сравнении (1) заменить простой модуль p составным модулем m, то
задача нахождения решений соответствующего сравнения становится намного
более сложной. Известные алгоритмы её решения основаны на сведении
сравнения к совокупности сравнений (1) по простым модулям – делителям m,
и, следовательно, они требуют разложения числа m на простые сомножители,
что, как уже указывалось, является достаточно трудоёмкой задачей.
3.2 Произведение и возведение в степень многочленов, заданных массивами
Условимся представлять многочлены массивами, индексированными, начиная с
0, в которых элемент с индексом i означает коэффициент многочлена
степени i
type
Polynome=array[1..Nmax] of Ring_Element;
Следующий алгоритм даёт функцию умножения двух многочленов и , где
многочлен степени (который даёт результат в конце алгоритма) должен быть
предварительно инициализирован нулём.
for i:= 0 to degP do
for j:= 0 to degQ do
R[i+j]:=R[i+j]+P[i](Q[i];
Изучая предыдущий алгоритм, устанавливаем, что его сложность как по
числу перемножений, так и сложений, равна произведению высот двух
многочленов: (deg P + 1)(degQ + 1), но в этом алгоритме, который не
учитывает случай нулевых коэффициентов, можно рассматривать высоту
многочлена как число всех коэффициентов. Значит, возможно улучшить
предыдущий алгоритм, исключив все ненужные перемножения:
for i:= 0 to degP do
if P[i] ( 0 then
for j:= 0 to degQ do
if Q[j] ( 0 then
R[i+j]:=R[i+j]+P[i]Q[i];
Очень просто вычислить сложность алгоритма возведения в степень
последовательными умножениями, если заметить, что когда P – многочлен
степени d, то Pi – многочлен степени id. Если обозначить Cmul(n)
сложность вычисления Pn, то рекуррентное соотношение Cmul(i + 1) =
Cmul(i) + (d +1)(id +1) даёт нам:
Cmul(n) = =
Что касается возведения в степень с помощью дихотомии (т.е.
повторяющимися возведениями в квадрат), вычисления несколько сложнее:
зная , вычисляем с мультипликативной сложностью. Как
следствие имеем:
Csqr(2l) = = =
=
Предварительное заключение, которое можно вывести из предыдущих
вычислений, складывается в пользу дихотомического возведения в степень:
если n есть степень двойки (гипотеза ad hoc), этот алгоритм ещё
выдерживает конкуренцию, даже если эта победа гораздо скромнее в данном
контексте (n2d2/3 против n2d2/2), чем когда работаем в Z/pZ (2log2 n
против n).
Но мы не учли корректирующие перемножения, которые должны быть
выполнены, когда показатель не является степенью двойки. Если n = 2l+1 –
1, нужно добавить к последовательным возведениям в квадрат перемножения
всех полученных многочленов. Умножение многочлена степени
(2i-1)d на многочлен степени 2id вносит свой вклад из ((2i – 1)d +
1)( 2i d + 1) умножений, которые, будучи собранными по всем
корректирующим вычислениям, дают дополнительную сложность:
= =
=
Теперь можно заключить, что дихотомическое возведение в степень не
всегда является лучшим способом для вычисления степени многочлена с
помощью перемножений многочленов. Число перемножений базисного кольца,
которые необходимы, Csqr(n), – в действительности заключено между
( ) и т.е. между n2d2/3 и 2n2d2/3, тогда как
простой алгоритм требует всегда n2d2/2 перемножений. В частности, если
исходный многочлен имеет степень, большую или равную 4, возведение в
степень наивным методом требует меньше перемножений в базисном кольце,
чем бинарное возведение в степень, когда n имеет форму 2l – 1.
Можно довольно просто доказать, что если n имеет вид 2l +2l – 1 + c
(выражения, представляющие двоичное разложение n), то метод вычисления
последовательными перемножениями лучше метода, использующего возведение
в квадрат (этот последний метод требует корректирующего счёта ценой, по
крайней мере, n2d2/9). Всё это доказывает, что наивный способ является
лучшим для этого класса алгоритмов, по крайней мере, в половине случаев.
Действительно, МакКарти [3] доказал, что дихотомический алгоритм
возведения в степень оптимален среди алгоритмов, оперирующих повторными
умножениями, если действуют с плотными многочленами (антоним к
разреженным) по модулю m, или с целыми и при условии оптимизации
возведения в квадрат для сокращения его сложности наполовину (в этом
случае сложность действительно падает приблизительно до n2d2/6 + n2d2/3
= n2d2/2).
3.3 Небольшие оптимизации для произведений многочленов
В принципе вычисление произведения двух многочленов степеней n и m
соответственно требует (n +1)( m +1) элементарных перемножений. Алгоритм
оптимизации возведения в квадрат состоит просто в применении формулы
квадрата суммы:
что даёт n +1 умножений для первого члена и n( n +1)/2 – для второго,
или в целом (n +1)( n +2)/2 умножений, что близко к половине
предусмотренных умножений, когда n большое.
Для произведения двух многочленов первой степени P = aX + b и Q = cX + d
достаточно легко находим формулы U = ac, W = bd, V = (a + b)(c + d) и PQ
= =UX2 + (V – U – W)X +W, в которых появляются только три элементарных
умножения, но четыре сложения. Можно рекурсивно применить этот процесс
для умножения двух многочленов P и Q степени 2l – 1, представляя их в
виде и применяя предыдущие формулы для вычисления PQ в
зависимости от A, B, C и D, где каждое произведение AB, CD и (A + B)(C +
D) вычисляется с помощью рекурсивного применения данного метода (это
метод Карацубы). Всё это даёт мультипликативную сложность ((2l) и
аддитивную сложность ((2l) такие, что:
((2l) = 3((2l – 1),…, ((2) = 3((1), ((1) = 1,
((2l) = 3((2l – 1) + 3(2l,…, ((2) = 3((1) + 6, ((1) = 1.
В этой последней формуле член 3(2l представляет собой число элементарных
сложений, необходимых, чтобы сделать два сложения многочленов степени
2l – 1 – 1 (a + b и c + d) и два вычитания многочленов степени 2l – 1
(U – V – W). Суммируя каждое из этих выражений, находим для n,
являющегося степенью двойки:
((n) = nlog3/log2 ( n1,585 и ((2) =7 nlog3/log2 – 6n.
К сожалению, этот принцип остаётся теоретическим, и на его основе нужно
построить итерационный алгоритм, чтобы получить разумную эффективность
(цена управления рекурсией очень велика).
3.4 Вычисление многочленов
Рассмотрим общую задачу вычисления многочлена n-й степени
u(x) = unxn + un – 1xn – 1 + … + u1x + u0, un ( 0, (1)
3.4.1 Схема Горнера
u(x) = (…(unx + un – 1)x + …)x + u0. (2)
Весь этот процесс требует n умножений и n сложений.
Было предложено несколько обобщений схемы Горнера. Посмотрим сначала,
как вычисляется в случае, когда – комплексное число, а коэффициенты
вещественны. Комплексное сложение и умножение можно очевидным образом
свести к последовательности обычных операций над вещественными числами:
вещественное + комплексное требует 1 сложение,
комплексное + комплексное требует 2 сложения,
вещественное ( комплексное требует 2 умножения,
комплексное ( комплексное требует 4 умножения и 2 сложения
или 3 умножения и 5 сложений.
Следовательно, схема Горнера (2) требует 4n – 2 умножений и 3n – 2
сложений или 3n – 1 умножений и 6n – 5 сложений для вычисления u(z),
когда z комплексное. Вот другая процедура для вычисления u(x + iy):
a1 = un, b1 = un – 1, r = x + x, s = x2 + y2; (3)
aj = bj – 1 + raj –1, bj = un – j – saj –1, 1
0, то правая часть сравнения (12) не превосходит p1/2 + (/2. Можно
доказать, что случайно выбранное натуральное число x Список литературы
Введение в криптографию под общей редакцией Ященко, М.: МЦНМО: «Черо»,
1999.
Алгебраическая алгоритмика, Ноден П., Китте К., М.: «Мир», 1999.
Coppersmith D., Odlyzko A. M., Schroeppel R. Descrete logarithms in
GF(p) // Algorithmica. V. 1,1986. P. 1-15.
Lenstra A. K, Lenstra H. W. (jr.) The Development of the Number Field
Siev. Lect. Notes in Math. V. 1554. Springer, 1993.
McCarthy D. P. “The optimal algorithm to evaluate xn using elementary
multiplication methods”, Math. Comp., vol. 31, no 137, 1977, pp. 251 –
256.
function DExp(x, n: LongInt): LongInt;
label 25, 99;
var c: LongInt;
begin
if n mod 2 ( 0 then
c : = x
else
c : = 1;
25: n : = n div 2;
if n = 0 then
goto 99;
x:= x(x;
if n mod 2 ( 0 then
c : = c(x;
goto 25;
99: DExp : = c;
end;
Нашли опечатку? Выделите и нажмите CTRL+Enter
