Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9 | Следующая страница реферата



((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 есть произведение малых простых чисел.

Рекомендуем скачать другие рефераты по теме: доклад 6 класс, здоровый образ жизни реферат.

Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9 | Следующая страница реферата