←предыдущая следующая→
1 2 3 4 5
элементарных перемножений. Алгоритм оп-тимизации возведения в квадрат состоит просто в применении формулы квад-рата суммы:
что даёт 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) + 32l,…, (2) = 3(1) + 6, (1) = 1.
В этой последней формуле член 32l представляет собой число элементарных сложений, необходимых, чтобы сделать два сложения многочленов степени 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 < j n.
Легко доказать индукцией по n, что u(z) = zan + bn. Эта схема требует 2n + 2 ум-ножений и 2n + 1 сложений, так что при n 3 она лучше схемы Горнера.
Рассмотрим процесс деления многочлена u(x) на многочлен x – x0. В резуль-тате такого деления мы получаем u(x) = (x – x0)q(x) + r(x); здесь deg(r) < 1, по-этому r(x) есть постоянная, не зависящая от x и u(x0) = 0q(x0) + r = r. Анализ этого процесса деления показывает, что вычисления почти те же самые, что в схеме Горнера для определения u(x0). Аналогично, когда мы делим u(z) на мно-гочлен (z – z0)(z – z0) = z2 – 2x0z + x02 + y02, то соответствующие вычисления эк-вивалентны процедуре (3); мы получаем
u(z) = (z – z0)(z – z0)q(z) + anz + bn;
следовательно,
u(z0) = anz0 + bn.
Вообще, когда мы делим u(x) на, f(x) получая u(x) = f(x) q(x) +¬ r(x), то из ра-венства f(x0) = 0 следует u(x0) = r(x0); это наблюдение ведёт к дальнейшим обобщениям правила Горнера. Мы можем положить, например, f(x) = x¬2 – x02; это даст нам схему Горнера «второго порядка»
u(x) = (…(u2 n/2 x2¬¬¬ + u2 n/2 – 2)x2 + u0 +
+((….u2 n/2 - 1 x2 + u2 n/2 - 3)x2 + … +)x2u1) x. (4)
3.4.2 Интерполяционная формула Ньютона и табулирование значений многочлена
Рассмотрим специальный случай вычисления многочлена. Интерполяцион-ный многочлен Ньютона степени n, определяемый формулой
u[n](x) = n(x – x0) (x – x1)…(x – xn – 1) +…+ n (x – x0) (x – x1) + 1 (x – x0) + 0, (5)
является единственным многочленом степени n от x, который принимает предписанные значения y0, y1, …, yn в заданных n + 1 различных точках x0, x1, …, xn соответственно. После того, как значения постоянных найдены, интер-поляционная формула Ньютона становится удобной для вычислений, так как мы можем, обобщив правило Горнера, записать
u[n](x) = ((…(n(x – xn – 1) + n – 1)(x – xn – 2) + …)(x – x1) + 1)
(x – x0) + 0. (6)
Теперь рассмотрим, как находятся постоянные в формуле Ньютона. Их можно определить, находя «разделённые разности» и сводя вычисления в сле-дующую таблицу (иллюстрирующую случай n = 3):
y0
(y1 – y0)/(x1 – x0) = y1
y1 (y2 – y’1)/(x2 – x0) = y2
(y2 – y1)/(x2 – x1) = y2 (y’’3 – y’’2)/(x3 – x0) = y3
y2 (y3 – y’2)/(x3 – x1) = y3
(y3 – y2)/(x3 – x2) = y3
y3 (7)
Можно доказать, что 0 = y0, 1 = y’1, 2 = y’2, и т. д. Следовательно, для нахож-дения величин может быть использована следующая вычислительная процеду-ра (соответствующая таблице (7)):
Начать с того, что установить (0, 1, …, n) (y0, y1, … , yn); затем для k = 1, 2, …, n (именно в таком порядке) установить yj (yj – yj – 1)/(xj – xj – k) для j = n, n – 1, …, k (именно в таком порядке).
Если мы хотим вычислить многочлен u(x) степени n сразу для многих зна-чений x, образующих арифметическую прогрессию (т. е. хотим вычислить u(x0), u(x0 + h), u(x0 + 2h),…), то весь процесс можно после нескольких первых шагов свести к одному только сложению вследствие того факта, что n-я разность от многочлена есть постоянная.
1 Найти коэффициенты n, …, 1, 0 представления нашего многочлена в виде интерполяционного многочлена Ньютона
u(x) = n / n! hn(x – x0 – (n – 1)h)…(x – x0 – h)(x – x0) +…+ 2 / 2! h2 (x – x0 – h)(x – x0) + 1 / h2 (x – x0) + 0. (8)
(Это можно сделать, беря повторные разности, в точности так же, как мы определяли выше постоянные в (5) (надо принять xj = x0 + jh), с тем ис-ключением, что все деления на xj – xj – k из вычислительной процедуры уст-раняются.)
2 Установить x x0.
3 Теперь значением u(x) является 0.
4 Установить j j + j + 1 для j = 0, 1, …, n – 1 (именно в таком порядке). Увеличить x на h и вернуться в шаг 3.
4. Дискретное логарифмирование
Пусть p – простое число. Ещё Эйлер знал, что мультипликативная группа кольца циклична, т. е. существуют такие целые числа а, что сравнение
ax b (mod p) (2)
разрешимо относительно x при любом bZ, не делящимся на p. Числа а с этим свойством называются первообразными корнями, и количество их равно (p – 1), где – функция Эйлера. Целое х, удовлетворяющее сравнению (2), называ-ется индексом или дискретным логарифмом числа b.
Выше мы описали алгоритм, позволяющий по заданному числу x достаточ-но быстро вычислять ах mod p. Обратная же операция – вычисление по задан-ному b его дискретного логарифма, вообще говоря, является очень сложной в вычислительном отношении задачей. Именно это свойство дискретного лога-рифма и используется в его многочисленных криптографических применениях. Наиболее быстрые (из известных) алгоритмы решения этой задачи, основанные на так называемом методе решета числового поля, требуют выполнения exp(c(ln p)1/3(ln ln p)2/3) арифметических операций, где c – некоторая положи-тельная постоянная. Это сравнимо со сложностью наиболее быстрых алгорит-мов разложения чисел на множители. Конечно, указанная оценка сложности получена при условии справедливости ряда достаточно правдоподобных гипо-тез.
Говоря о сложности задачи дискретного логарифмирования, мы имели в ви-ду «общий случай». Ведь и большое целое число легко может быть разложено на простые сомножители, если все эти сомножители не очень велики. Известен алгоритм, позволяющий быстро решать задачу дискретного логарифмирования, если p – 1 есть произведение малых простых чисел.
Пусть q – простое число, делящее р – 1. Обозначим с а(p – 1)/q (mod p), тогда классы вычетов 1, с, с2, … , сq – 1 все различны и образуют полное множество решений уравнения хq = 1 в поле Fp = Z/Zp. Если q не велико и целое число d удовлетворяет сравнению хq 1 (mod p), то показатель k, 0 k < q, для которого выполняется d ck (mod p), легко может быть найден, например, с помощью перебора. Именно на этом свойстве основан упомянутый выше алгоритм.
Допустим, что р – 1 = qkh, (q,h) = 1. Алгоритм последовательно строит це-лые
←предыдущая следующая→
1 2 3 4 5