Быстрые вычисления с целыми числами и полиномами
сложность ((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 < 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) =
0(q(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) =
x2 – 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) = y(1
y1 (y2 – y’1)/(x2 – x0) = y((2
(y2 – y1)/(x2 – x1) = y(2 (y’’3 – y’’2)/(x3 –
x0) = y(((3
y2 (y3 – y’2)/(x3 – x1) = y((3
(y3 – y2)/(x3 – x2) = y(3
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 при любом b(Z, не делящимся на 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. Алгоритм последовательно строит
целые числа uj, j = 0,1,…,k, для которых выполняется сравнение
( 1 (mod p).
(3)
Так как выполняется сравнение ( 1 (mod p), то найдётся целое число
u0, для которого ( (mod p). При таком выборе сравнение (3) с j =
0, очевидно, выполняется. Предположим, что найдено число uj,
удовлетворяющее сравнению (3). Тогда определим t с помощью сравнения
( ct (mod p),
(4)
и положим. Имеют место сравнения
( ( 1
| |  скачать работу |
Быстрые вычисления с целыми числами и полиномами |
