Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

вещественное  комплексное требует 2 умножения,

комплексное  комплексное требует 4 умножения и 2 сложения

или 3 умножения и 5 сложений.

Следовательно, схема Горнера (2) требует 4n – 2 умножений и 3n – 2 сложений или 3n – 1 умножений и 6n – 5 сложений для вычисления u(z), когда z комплексное. Вот другая процедура для вычисления u(x + iy):

a₁ = u_n, b₁ = u_{n – 1}, r = x + x, s = x² + y²; (3)

a_j = b_{j – 1} + ra_{j –1}, b_j = u_{n – j} – sa_{j –1}, 1 < j  n.

Легко доказать индукцией по n, что u(z) = za_n + b_n. Эта схема требует 2n + 2 умножений и 2n + 1 сложений, так что при n  3 она лучше схемы Горнера.

Рассмотрим процесс деления многочлена u(x) на многочлен x – x₀. В результате такого деления мы получаем u(x) = (x – x₀)q(x) + r(x); здесь deg(r) < 1, поэтому r(x) есть постоянная, не зависящая от x и u(x₀) = 0q(x₀) + r = r. Анализ этого процесса деления показывает, что вычисления почти те же самые, что в схеме Горнера для определения u(x₀). Аналогично, когда мы делим u(z) на многочлен (z – z₀)(z – z₀) = z² – 2x₀z + x₀² + y₀², то соответствующие вычисления эквивалентны процедуре (3); мы получаем

u (z) = (z – z₀)(z – z₀)q(z) + a_nz + b_n;

следовательно,

u(z₀) = a_nz₀ + b_n.

Вообще, когда мы делим u(x) на, f(x) получая u(x) = f(x) q(x) +­ r(x), то из равенства f(x₀) = 0 следует u(x₀) = r(x₀); это наблюдение ведёт к дальнейшим обобщениям правила Горнера. Мы можем положить, например, f(x) = x­² – x₀²; это даст нам схему Горнера «второго порядка»

u(x) = (…(u_{2 n/2 } x²­­­ + u_{2 n/2  – 2})x² + u₀ +

+((….u_{2 n/2  - 1} x² + u_{2 n/2  - 3})x² + … +)x²u₁) x. (4)

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

Рассмотрим специальный случай вычисления многочлена. Интерполяционный многочлен Ньютона степени n, определяемый формулой

u^[n](x) = _n(x – x₀) (x – x₁)…(x – x_{n – 1}) +…+ _n (x – x₀) (x – x₁) + ₁ (x – x₀) + ₀, (5)

является единственным многочленом степени  n от x, который принимает предписанные значения y₀, y₁, …, y_n в заданных n + 1 различных точках x₀, x₁, …, x_n соответственно. После того, как значения постоянных  найдены, интерполяционная формула Ньютона становится удобной для вычислений, так как мы можем, обобщив правило Горнера, записать

u^[n](x) = ((…(_n(x – x_{n – 1}) + _{n – 1})(x – x_{n – 2}) + …)(x – x₁) + ₁)

(x – x₀) + ₀. (6)

Теперь рассмотрим, как находятся постоянные  в формуле Ньютона. Их можно определить, находя «разделённые разности» и сводя вычисления в следующую таблицу (иллюстрирующую случай n = 3):

y₀

(y₁ – y₀)/(x₁ – x₀) = y₁

y₁ (y₂ – y’₁)/(x₂ – x₀) = y₂

(y₂ – y₁)/(x₂ – x₁) = y₂ (y’’₃ – y’’₂)/(x₃ – x₀) = y₃

y₂ (y₃ – y’₂)/(x₃ – x₁) = y₃

(y₃ – y₂)/(x₃ – x₂) = y₃

y₃ (7)

Можно доказать, что ₀ = y₀, ₁ = y’₁, ₂ = y’₂, и т. д. Следовательно, для нахождения величин может быть использована следующая вычислительная процедура (соответствующая таблице (7)):

Начать с того, что установить (₀, ₁, …, _n)  (y₀, y₁, … , y_n); затем для k = 1, 2, …, n (именно в таком порядке) установить y_j  (y_j – y_{j – 1})/(x_j – x_{j – k}) для j = n, n – 1, …, k (именно в таком порядке).

Если мы хотим вычислить многочлен u(x) степени n сразу для многих значений x, образующих арифметическую прогрессию (т. е. хотим вычислить u(x₀), u(x₀ + h), u(x₀ + 2h),…), то весь процесс можно после нескольких первых шагов свести к одному только сложению вследствие того факта, что n-я разность от многочлена есть постоянная.

1. Найти коэффициенты _n, …, ₁, ₀ представления нашего многочлена в виде интерполяционного многочлена Ньютона

u(x) = _n / n! hⁿ(x – x₀ – (n – 1)h)…(x – x₀ – h)(x – x₀) +…+ ₂ / 2! h² (x – x₀ – h)(x – x₀) + ₁ / h² (x – x₀) + ₀. (8)

(Это можно сделать, беря повторные разности, в точности так же, как мы определяли выше постоянные  в (5) (надо принять x_j = x₀ + jh), с тем исключением, что все деления на x_j – x_{j – k} из вычислительной процедуры устраняются.)

1. Установить x  x₀.

2. Теперь значением u(x) является ₀.

3. Установить _j  _j + _{j + 1} для j = 0, 1, …, n – 1 (именно в таком порядке). Увеличить x на h и вернуться в шаг 3.

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

Пусть p – простое число. Ещё Эйлер знал, что мультипликативная группа кольца циклична, т. е. существуют такие целые числа а, что сравнение

a^x  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, с, с², … , с^{q – 1} все различны и образуют полное множество решений уравнения х^q = 1 в поле F_p = Z/Z_p. Если q не велико и целое число d удовлетворяет сравнению х^q  1 (mod p), то показатель k, 0  k < q, для которого выполняется d  c^k (mod p), легко может быть найден, например, с помощью перебора. Именно на этом свойстве основан упомянутый выше алгоритм.

Д опустим, что р – 1 = q^kh, (q,h) = 1. Алгоритм последовательно строит целые числа u_j, j = 0,1,…,k, для которых выполняется сравнение

 1 (mod p). (3)

Т ак как выполняется сравнение  1 (mod p), то найдётся целое число u₀, для которого  (mod p). При таком выборе сравнение (3) с j = 0, очевидно, выполняется. Предположим, что найдено число u_j, удовлетворяющее сравнению (3). Тогда определим t с помощью сравнения

 c^t (mod p), (4)

и положим. Имеют место сравнения

  1 (mod p), (5)

о значающие справедливость (3) при j + 1.

При j = k сравнение означает в силу (2), что  1 (mod p). Целое число а есть первообразный корень по модулю р, поэтому имеем (x – u_k)h  0 (mod p – 1) и

x  u_k (mod q^k).

Е сли , где все простые числа q_j малы, то указанная процедура позволяет найти вычеты x mod , i = 1,…,s, и, с помощью китайской теоремы об остатках, вычет x mod p – 1, т. е. решить сравнение (2).

В случае обычных логарифмов в поле действительных чисел имеется специальное основание e = 2,171828…, позволяющее достаточно быстро вычислять логарифмы с произвольной точностью. Например, это можно делать с помощью быстро сходящегося ряда

ln(1+x)/(1 – x) = 2(x + x³/3 + x⁵/5 + …), |x| < 1. (6)

Логарифмы по произвольному основанию с могут быть вычислены с помощью тождества

log_c x = ln x/ ln c. (7)

В случае дискретных логарифмов нет основания, по которому логарифмы вычислялись бы столь же быстро, как натуральные в поле действительных чисел. Вместе с тем, последняя формула, связывающая логарифмы с различными основаниями, остаётся справедливой и позволяет выбирать основание удобным способом. Единственное условие для этого состоит в том, чтобы логарифм нового основания Log c был взаимно прост c p - 1. Тогда в формуле (7) возможно деление по модулю р – 1. Заметим, что это условие будет выполнено, если и только если с – первообразный корень. Из расширенной гипотезы Римана следует, что наименьший первообразный корень по модулю р ограничен величиной O(log⁶ p). Поэтому в дальнейшем для простоты изложения мы будем предполагать, что основание а в (2) невелико, именно а = O(log⁶ p).

Т ак как поле Fp неполно, вычисление дискретных логарифмов не может использовать предельный переход и основано на иных принципах. Прежде всего, нужный дискретный логарифм log b вычисляется не сам по себе, а вместе с совокупностью логарифмов ряда других чисел. Заметим, что всякое сравнение вида

 (mod p), (8)

где q_i, k_i, m_i  Z приводит к соотношению между логарифмами

Характеристики

Список файлов реферата