Реферат: Быстрые вычисления с целыми числами и полиномами

Теперь рассмотрим, как находятся постоянные a в формуле Ньютона. Их можно определить, находя «разделённые разности» и сводя вычисления в следующую таблицу (иллюстрирующую случай 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)

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

Начать с того, что установить (a₀ , a₁ , …, a_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 Найти коэффициенты b_n , …, b₁ , b₀ представления нашего многочлена в виде интерполяционного многочлена Ньютона

u (x ) = b_n / n ! hⁿ (x – x ₀ – (n – 1)h )…(x – x ₀ – h )(x – x ₀ ) +…+ b₂ / 2! h ² **(x – x ₀ – h )(x – x ₀ ) + b₁ / h ² (x – x ₀ ) + b₀ . (8)

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

2 Установить x ¬x ₀ .

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

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

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

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

a^x ºb (mod p ) (2)

разрешимо относительно x при любом b ÎZ, не делящимся на p . Числа а с этим свойством называются первообразными корнями, и количество их равно j(p – 1), где j – функция Эйлера. Целое х , удовлетворяющее сравнению (2), называется индексом или дискретным логарифмом числа b .

Выше мы описали алгоритм, позволяющий по заданному числу x достаточно быстро вычислять а^х modp . Обратная же операция – вычисление по заданному b его дискретного логарифма, вообще говоря, является очень сложной в вычислительном отношении задачей. Именно это свойство дискретного логарифма и используется в его многочисленных криптографических применениях. Наиболее быстрые (из известных) алгоритмы решения этой задачи, основанные на так называемом методе решета числового поля, требуют выполнения exp(c (lnp )^1/3 (lnlnp )^2/3 ) арифметических операций, где c – некоторая положительная постоянная. Это сравнимо со сложностью наиболее быстрых алгоритмов разложения чисел на множители. Конечно, указанная оценка сложности получена при условии справедливости ряда достаточно правдоподобных гипотез.

Говоря о сложности задачи дискретного логарифмирования, мы имели в виду «общий случай». Ведь и большое целое число легко может быть разложено на простые сомножители, если все эти сомножители не очень велики. Известен алгоритм, позволяющий быстро решать задачу дискретного логарифмирования, если p – 1 есть произведение малых простых чисел.

Пусть q – простое число, делящее р – 1. Обозначим с ºа ^{( p – 1)/ q} (modp ), тогда классы вычетов 1, с , с ² , … , с ^{q – 1} все различны и образуют полное множество решений уравнения х ^q = 1 в поле F_p = Z/Z_p . Если q не велико и целое число d удовлетворяет сравнению х ^q º 1 (modp ), то показатель k , 0 £k < q , для которого выполняется d ºc^k (modp ), легко может быть найден, например, с помощью перебора. Именно на этом свойстве основан упомянутый выше алгоритм.

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

º 1 (modp ). (3)

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

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

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

ºº 1 (modp ), (5)

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

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

x ºu_k (mod q^k ).