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

Карацубы). Всё это даёт мультипликативную сложность ((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):

(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

(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 (mod p), (5)

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

При j = k сравнение означает в силу (2), что ( 1 (mod p). Целое

число а есть первообразный корень по модулю р, поэтому имеем (x – uk)h ( 0

(mod p – 1) и

x ( uk (mod qk).

Если , где все простые числа qj малы, то

указанная процедура позволяет найти вычеты x mod , i = 1,…,s, и, с

помощью китайской теоремы об остатках, вычет x mod p – 1, т. е. решить

сравнение (2).

В случае обычных логарифмов в поле действительных чисел имеется

специальное основание e = 2,171828…, позволяющее достаточно быстро

вычислять логарифмы с произвольной точностью. Например, это можно делать с

помощью быстро сходящегося ряда

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

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

тождества

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

В случае дискретных логарифмов нет основания, по которому логарифмы

вычислялись бы столь же быстро, как натуральные в поле действительных

чисел. Вместе с тем, последняя формула, связывающая логарифмы с различными

основаниями, остаётся справедливой и позволяет выбирать основание удобным

способом. Единственное условие для этого состоит в том, чтобы логарифм

нового основания Log c был взаимно прост c p - 1. Тогда в формуле (7)

возможно деление по модулю р – 1. Заметим, что это условие будет выполнено,

если и только если с – первообразный корень. Из расширенной гипотезы Римана

следует, что наименьший первообразный корень по модулю р ограничен

величиной O(log6 p). Поэтому в дальнейшем для простоты изложения мы будем

предполагать, что основание а в (2) невелико, именно а = O(log6 p).

Так как поле Fp неполно, вычисление дискретных логарифмов не может

использовать предельный переход и основано на иных принципах. Прежде всего,

нужный дискретный логарифм log b вычисляется не сам по себе, а вместе с

совокупностью логарифмов ряда других чисел. Заметим, что всякое сравнение

вида

( (mod p), (8)

где qi, ki, mi ( Z приводит к соотношению между логарифмами

(k1 – m1)Log q1 + … + (ks – ms)Log qs ( 0 (mod p – 1). (9)

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

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

p),

то

r1Log q1 +…+ rsLog qs ( 1 (mod p – 1) (10)

Log b ( x1Log q1 +…+ xsLog qs (mod p – 1) (11)

Имея достаточно много векторов k1,…,ks, m1,…,ms с условием (8), можно найти

решение соответствующей системы сравнений (9), (10). Если эта система имеет

единственное решение, то им как раз и будет набор логарифмов Log q1,…,Log

qs. Затем с помощью (11) можно найти Log b.

Мы опишем ниже реализацию этой идеи, взятую из работы [1]. Эвристические

соображения позволили авторам этой работы утверждать, что предложенный ими

алгоритм требует L1 + (, где L = , арифметических

операций для вычисления Log b.

Положим

H = [ ] + 1, J = H2 – q.

Тогда 0 < J < 2 + 1, и, как легко проверить, для любой пары целых

чисел с1, с2 выполняется сравнение

(H + c1) (H + c2) ( J + (c1 + c2)H + c1c2 (mod p). (12)

Если числа ci не очень велики, скажем ci ( L1/2 + ( при некотором ( > 0,

то правая часть сравнения (12) не превосходит p1/2 + (/2. Можно доказать,

что случайно выбранное натуральное число x < p1/2 + (/2 раскладывается в

произведение простых чисел, меньших с вероятностью, большей, чем L-1/2 -

(/2.

Обозначим через S = {q1,…,qs} совокупность всех простых чисел q < L1/2,

а также всех простых чисел вида H + c при 0 < c < L1/2 + (. Тогда s =

O(L1/2 + (). Будем теперь перебирать случайным образом числа и для каждой

такой пары пытаться разложить на множители соответствующее выражение из

правой части (12). Для разложения можно воспользоваться, например, делением

на все простые числа, меньшие, чем L1/2. Перебрав все (L1/2 + ( )2/2 = O(L1

+ 2( ) указанных пар с1, с2 мы найдём, как это следует из указанных выше

вероятностных соображений, не менее

L-1/2 - (/2 *O(L1 + 2( ) = O(L1/2 + 3(/2) (13)

пар, для которых правая часть сравнения (12) полностью раскладывается на

простые сомножители, меньшие L1/2. Сравнение (12), таким образом, принимает

вид (8). Так строится система уравнений типа (9).

Напомним, что число а, согласно нашему предположению, существенно

меньше, чем L1/2. Поэтому оно раскладывается в произведение простых чисел,

входящих во множество {q1,…,qs}, и это приводит к сравнению (10).

Заметим, что количество (13) найденных сравнений типа (9) превосходит

число s. Следовательно, построенная система неоднородных линейных сравнений

относительно Log qi содержит сравнений больше, чем неизвестных. Конечно,

множество её решений может при этом быть бесконечным. Одна из

правдоподобных гипотез состоит в том, что система имеет всё-таки

единственное решение, и, решив её, можно определить дискретные логарифмы

всех чисел qi. На этом завершается первый этап работы алгоритма из [1].

Как было отмечено, каждое из чисел, стоящих в правой части сравнения

(12), не превосходит p1/2 + (/2. Поэтому оно раскладывается в произведение

не более O(ln p) простых сомножителей и, следовательно, каждое из сравнений

(9) построенной системы содержит лишь O(ln p) отличных от нуля

коэффициентов. Матрица системы сравнений будет разреженной, что позволяет

применять для её решения специальные методы с меньшей оценкой сложности,

чем обычный гауссов метод исключения переменных.

Вместо перебора всех допустимых значений ci в [1] предлагается

использовать так называемое решето, отбрасывающее все пары этих чисел, для

которых правая часть (12) заведомо не раскладывается в произведение малых

простых сомножителей. Для каждого c1 и каждой малой простой степени q' <

L1/2 можно найти все решения c2 < L1/2 линейного сравнения

J + (c1 + c2)H + c1c2 ( 0 (mod q').

Организованная правильным образом, эта процедура одновременно отбирает все

нужные пары чисел c1,c2 и даёт разложение на простые сомножители правых

частей сравнений (12).

Итак, после первого этапа работы алгоритма в нашем распоряжении

оказываются дискретные логарифмы всех чисел из множества S. Второй этап

алгоритма сводит поиск дискретного логарифма числа b к поиску логарифмов

некоторого множества чисел u, не превосходящих по величине L2. Выбирая

случайным образом число ( не более L1/4 раз, можно, как показывают

вероятностные соображения, найти такое (, что вычет a(b mod p

раскладывается в произведение простых чисел, меньших L2. Пусть

(mod p)

такое разложение, где u1,…,ut – некоторые простые числа с условием L1/2 < u

< < L2. На поиск этого сравнения потребуется O(L1/2)арифметических

операций. В результате вычисление дискретного логарифма числа b сводится к

вычислению t дискретных логарифмов для чисел uj, 1 ( j ( t среднего

размера.

Наконец, на последнем этапе производится вычисление логарифмов всех

чисел uj. Пусть u – простое число из интервала условием L1/2 < u < L2.

Обозначим

G = [(p / u], I = HGu – p.

Для любых целых чисел c1, c2 < L1/2 + ( выполняется сравнение

(H + c1) (H + c2)u ( I + (c1G+ c2H + c1c2 )u (mod p). (14)

Отметим, что правая часть этого сравнения не превосходит p1/2 L5/2 + (.

Просеивая все числа c1, c2 из указанного интервала, можно найти такие, что

числа G+ c2 и правая часть сравнения (14) состоят из простых сомножителей,

не превосходящих L1/2. Тогда сравнение (14) позволяет вычислить Log u.

Вычисление Log b при известных уже значениях Log q1 требует L1/2 + (

арифметических операций.

Существуют и другие способы построения соотношений (8). В [2] для этого

используются вычисления в полях алгебраических чисел. В качестве множителей

в соотношения типа (8) используются не только простые числа, но и простые

идеалы с небольшой нормой.

Задача вычисления дискретных логарифмов может рассматриваться также и в

полях Fpn, состоящих из pn элементов, в мультипликативных группах классов

вычетов (Z/mZ)*, в группах точек эллиптических кривых и вообще в

произвольных группах.

Список литературы

1. Введение в криптографию под общей редакцией Ященко, М.: МЦНМО:

«Черо», 1999.

2. Алгебраическая алгоритмика, Ноден П., Китте К., М.: «Мир», 1999.

1] Coppersmith D., Odlyzko A. M., Schroeppel R. Descrete logarithms in

GF(p) // Algorithmica. V. 1,1986. P. 1-15.

2] Lenstra A. K, Lenstra H. W. (jr.) The Development of the Number Field

Siev. Lect. Notes in Math. V. 1554. Springer, 1993.

3] McCarthy D. P. “The optimal algorithm to evaluate xn using elementary

multiplication methods”, Math. Comp., vol. 31, no 137, 1977, pp. 251 –

256.

-----------------------

[pic]

function DExp(x, n: LongInt): LongInt;

label 25, 99;

var c: LongInt;

begin

if n mod 2 ( 0 then

c : = x

else

c : = 1;

25: n : = n div 2;

if n = 0 then

goto 99;

x:= x(x;

if n mod 2 ( 0 then

c : = c(x;

goto 25;

99: DExp : = c;

end;

[pic]

Страницы: 1, 2

МЕНЮ

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

ИНТЕРЕСНОЕ