Быстрые вычисления с целыми числами и полиномами (стр. 4 из 5)

*(x – x₀) + a₀. (6)

Теперь рассмотрим, как находятся постоянные 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^kh, (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).

Если , где все простые числа q_j малы, то указанная процедура позволяет найти вычеты xmod, i = 1,…,s, и, с помощью китайской теоремы об остатках, вычет xmodp – 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)

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

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

º (mod p), (8)

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

(k₁ – m₁)Log q₁ + … + (k_s – m_s)Log q_sº 0 (mod p – 1). (9)

А если выполняются сравнения

aº(mod p – 1) bº(mod p),

то

r₁Log q₁ +…+ r_sLog q_sº 1 (mod p – 1) (10)

и

Log bº x₁Log q₁ +…+ x_sLog q_s (mod p – 1) (11)

Имея достаточно много векторов k₁,…,k_s,m₁,…,m_s с условием (8), можно найти решение соответствующей системы сравнений (9), (10). Если эта система имеет единственное решение, то им как раз и будет набор логарифмов Logq_1,…,Logq_s. Затем с помощью (11) можно найти Logb.