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

Министерство образования Российской Федерации

Ярославский Государственный Университет им. П.Г. Демидова

Курсовая работа

По дисциплине «Алгебра»

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

Выполнил: Студент группы КБ-11

Сбоев А.В.

Проверил: Дурнев В.Г.

Ярославль, 2003
Содержание

1. Введение. Сложность теоретико-числовых алгоритмов.

2. Полиномиальные алгоритмы

2.1 Алгоритм вычисленияa^d modm

2.2 Дихотомический алгоритм возведения в степень

2.3 Алгоритм Евклида

2.4 Алгоритм решения уравненияax + by = 1

3. Полиномиальная арифметика

3.1 Алгоритм нахождения делителей многочлена f (x ) в кольцеF_p [x ]

3.2 Произведение и возведение в степень многочленов, заданных массивами

3.3 Небольшие оптимизации для произведения многочленов

3.4 Вычисление полиномов

3.4.1 Схема Горнера

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

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

1. Введение. Сложность теоретико-числовых алгоритмов

Сложность алгоритмов теории чисел обычно принято измерять количеством арифметических операций (сложений, вычитаний, умножений и делений с остатком), необходимых для выполнения всех действий, предписанных алгоритмом. Впрочем, это определение не учитывает величины чисел, участвующих в вычислениях. Ясно, что перемножить два стозначных числа значительно сложнее, чем два однозначных, хотя при этом и в том, и в другом случае выполняется лишь одна арифметическая операция. Поэтому иногда учитывают ещё и величину чисел, сводя дело к так называемым побитовым операциям, т. е. Оценивая количество необходимых операций с цифрами 0 и 1, в двоичной записи чисел. Это зависит от рассматриваемой задачи, целей автора и т. д.

На первый взгляд странным также кажется, что операции умножения и деления приравниваются по сложности к операциям сложения и вычитания. Житейский опыт подсказывает, что умножать числа значительно сложнее, чем складывать их. В действительности же, вычисления можно организовать так, что на умножение или деление больших чисел понадобится не намного меньше битовых операций, чем на сложение. Существует алгоритм Шенхаге – Штрассена, основанный на так называемом быстром преобразовании Фурье, и требующий O (n ln n lnln n ) битовых операций для умножения двух n-разрядных двоичных чисел. Таким же количеством битовых операций можно обойтись при выполнении деления с остатком двух двоичных чисел, записываемых не более чем n цифрами. Для сравнения отметим, что сложение n -разрядных двоичных чисел требует O (n ) битовых операций.

Говоря о сложности алгоритмов, мы будем иметь в виду количество арифметических операций. При построении эффективных алгоритмов и обсуждении верхних оценок сложности обычно хватает интуитивных понятий той области математики, которой принадлежит алгоритм. Формализация же этих понятий требуется лишь тогда, когда речь идёт об отсутствии алгоритма или доказательстве нижних оценок сложности.

2. Полиномиальные алгоритмы

Четыре приведённых ниже алгоритма относятся к разряду так называемых полиномиальных алгоритмов. Это название носят алгоритмы, сложность которых оценивается сверху степенным образом в зависимости от длины записи входящих чисел. Если наибольшее из чисел, подаваемых на вход алгоритма, не превосходит m , то сложность алгоритмов этого типа оценивается величиной O (ln^c m ), где c – некоторая абсолютная постоянная. Во всех приведённых примерах с =1.

Следующий алгоритм вычисляет a^d modm . При этом, конечно, предполагается, что натуральные числа a и d не превосходят по величине m .

2.1 Алгоритм вычисления a^d modm

1. Представим d в двоичной системе счисления d =d ₀ 2^r +…+ d_{r -1} 2+ d_r , где d_i , цифры в двоичном представлении, равны 0 или 1, d ₀ = 1.

2. Положим a ₀ = a и затем для i = 1,…,r вычислим a_i ºa ² _{i -1} a^di (modm ).

3. a_r есть искомый вычетa^d modm .

Справедливость этого алгоритма вытекает из сравнения

a_i ºa² _i-1 a^{d 0 2^i+…+di} (mod m ),

легко доказываемого индукцией по i .

Так как каждое вычисление на шаге 2 требует не более трёх умножений по модулю m и этот шаг выполняется r £log₂ m раз, то сложность алгоритма может быть оценена величиной O (lnm ).

2.2 Дихотомический алгоритм возведения в степень.

В общем виде дихотомический алгоритм позволяет вычислить n –ю степень в моноиде. Будучи применён к множеству целых чисел с операцией сложения, этот метод позволяет умножать два целых числа и более известен как египетское умножение.

Классический алгоритм возведения в степень посредством последовательного умножения характерен, главным образом, своей неэффективностью в обычных обстоятельствах – его время работы линейным образом зависит от показателя степени.

Возьмём моноид М с операцией умножения и рассмотрим некоторый элемент x ₀ из М , а также произвольное натуральное число n ₀ . Для того, чтобы вычислить , представим n ₀ в двоичной системе счисления:

n ₀ = b_t 2^t + b_{t – 1} 2^{t – 1} + … + b ₁ 2¹ + b ₀ 2⁰ ,

предполагая, что n ₀ содержит (t + 1)двоичных цифр (т. е. что b_t ¹ 0 и b_{t + 1} = 0). В этих условиях вычисляемое выражение может быть записано:

или же .

Если задана последовательность (x_i )_{0 £ i £ t} , первый элемент которой есть x ₀ и x_i для i Î [1,t ] определено соотношением x_i = x_{i – 1} ² , то можно записать = P{x_i | 0 £i £t , b_i ¹ 0}. Чтобы завершить построение алгоритма и иметь возможность получить значение предыдущего произведения, необходимо вычислить биты b_i числа n ₀ . Для последовательности (n_i ) _{0 £ i £ t +1} (с начальным элементом n ₀ ), определённой соотношением n_i = [n_{i – 1} /2] для любого i Î [1, t + 1], бит b_i равен нулю, если n_i чётно, и равен единице в противном случае. Первое значение индекса i , для которого n_i равно нулю, есть t + 1.

Ясно, что число итераций, необходимых для выполнения алгоритма, зависит только от показателя n .

2^t £n £ 2^{t + 1} илиt £ log₂ n < t + 1.

Первая часть этого свойства может быть выражена следующим образом: [n /2^{t + 1} ] = 0 и [n /2^t ] ¹ 0, что позволяет точно определить число совершаемых делений n , равное числу итераций алгоритма при заданном значении n . Очевидно, нужно совершить t + 1 итераций, чтобы выполнить алгоритм, т. е. [log₂ n ] + 1 итераций. Следовательно, трудоёмкость алгоритма есть O (logn ).

Третий алгоритм – это классический алгоритм Евклида вычисления наибольшего общего делителя целых чисел. Мы предполагаем заданными два натуральных числа a и b и вычисляем их наибольший общий делитель (a ,b ).

2.3 Алгоритм Евклида

1. Вычислим r – остаток от деления числа a на b , a = bq +r , 0 £r < b .

2. Если r = 0, то b есть искомое число.

3. Если r ¹ 0, то заменим пару чисел (a ,b ) парой (b ,r ) и перейдём к шагу1.

Не останавливаясь на объяснении, почему алгоритм действительно находит (a ,b ), докажем некоторую оценку его сложности.

Теорема 1. При вычислении наибольшего общего делителя ( a , b ) с помощью алгоритма Евклида будет выполнено не более 5p операций деления с остатком, где p есть количество цифр в десятичной записи меньшего из чисел a и b .

Доказательство. Положим r ₀ = a > b и определим r ₁ ,r ₂ ,…,r_n - последовательность делителей, появляющихся в процессе выполнения шага 1 алгоритма Евклида. Тогда

r₁ = b ,…, 0£ r_i+1 < r_i , i = 0,1,…,n - 1.

Пусть также u ₀ = 1,u ₁ = 1,u_{k +1} = u_k + u_{k -1} ,k ³ 1, - последовательность Фибоначчи. Индукцией по i от i = n - 1 до i = 0 легко доказывается неравенство r_{i +1} ³u_{n - i} . А так как u_n ³ 10^{( n -1)/5} , то имеем неравенства 10^p > b = r ₁ ³u_n ³ 10^{( n -1)/5} и n < 5p +1.

Немного подправив алгоритм Евклида, можно достаточно быстро решать сравнения ax º 1 (modm ) при условии, что (a ,b ) = 1. Эта задача равносильна поиску целых решений уравнения ax + by = 1.

2.4 Алгоритм решения уравнения ax + by = 1

0. Определим матрицу E =

1. Вычислим r – остаток от деления числа a на b , a = bq + r , 0 £r < b .

2. Если r = 0, то второй столбец матрицы Е даёт вектор (x y ) решений уравнения.

3. Если r ¹ 0, то заменим матрицу Е матрицей

4. Заменим пару чисел (a ,b ) парой (b ,r ) и перейдём к шагу 1.

Если обозначить через Е _k матрицу Е , возникающую в процессе работы алгоритма перед шагом 2 после k делений с остатком (шаг 1), то в обозначениях из доказательства теоремы 1 в этот момент выполняется векторное равенство (a ,b )*E_k = (r_{k -1} ,r_k ). Его легко доказать индукцией по k . Поскольку числа a и b взаимно просты, имеем r_n = 1, и это доказывает, что алгоритм действительно даёт решение уравнения ax + by = 1. Буквой n мы обозначили количество делений с остатком, которое в точности такое же, как и в алгоритме Евклида.

Полиномиальные алгоритмы в теории чисел – большая редкость. Да и оценки сложности алгоритмов чаще всего опираются на какие-либо не доказанные, но правдоподобные гипотезы, обычно относящиеся к аналитической теории чисел.

Для некоторых задач эффективные алгоритмы вообще не известны. Иногда в таких случаях всё же можно предложить последовательность действий, которая, «если повезёт», быстро приводит к требуемому результату. Существует класс так называемых вероятностных алгоритмов, которые дают правильный результат, но имеют вероятностную оценку времени работы. Обычно работа этих алгоритмов зависит от одного или нескольких параметров. В худшем случае они работают достаточно долго. Но удачный выбор параметра определяет быстрое завершение работы. Такие алгоритмы, если множество «хороших» значений параметров велико, на практике работают достаточно эффективно, хотя и не имеют хороших оценок сложности.

3. Полиномиальная арифметика

Рассмотрим вероятностный алгоритм, позволяющий эффективно находить решения полиномиальных сравнений по простому модулю. Пусть p – простое число, которое предполагается большим, и f (x )ÎZ[x ] – многочлен, степень которого предполагается ограниченной. Задача состоит в отыскании решений сравнения

f (x ) º 0 (mod p ). (1)

Например, речь может идти о решении квадратичных сравнений, если степень многочлена f (x ) равна 2. Другими словами, мы должны отыскать в поле F_p = Z/p Z все элементы, удовлетворяющие уравнению f (x ) = 0.

Согласно малой теореме Ферма, все элементы поля F_p являются однократными корнями многочлена x^p - x . Поэтому, вычислив наибольший общий делитель d (x ) = (x^p - x , f (x )), мы найдём многочлен d (x ), множество корней которого в поле F_p совпадает с множеством корней многочлена f (x ), причём все эти корни однократны. Если окажется, что многочлен d (x ) имеет нулевую степень, т. е. лежит в поле F_p , это будет означать, что сравнение (1) не имеет решений.

Для вычисления многочлена d (x ) удобно сначала вычислить многочлен c (x )ºx^p (mod f (x )), пользуясь алгоритмом, подобным описанному выше алгоритму возведения в степень (напомним, что число p предполагается большим). А затем с помощью аналога алгоритма Евклида вычислить d (x ) = (c (x ) – x , f (x )). Всё это выполняется за полиномиальное количество арифметических операций.

Таким образом, обсуждая далее задачу нахождения решений сравнения (1) мы можем предполагать, что в кольце многочленов F_p [x ] справедливо равенство

f (x ) = (x – a₁ )*…*(x – a_n ), a_i ÎF_p , a_i ¹a_j .

3. 1 Алгоритм нахождения делителей многочлена f ( x ) в кольце F_p [ x ]

1. Выберем каким-либо способом элемент d Î F_p .

2. Вычислим наибольший общий делитель

g (x ) = ( f (x ), (x + d )^(p-1)/2 – 1).

3. Если многочлен g (x ) окажется собственным делителем f (x ), то многочлен f (x ) распадается на два множителя и с каждым из них независимо нужно будет проделать все операции, предписываемые настоящим алгоритмом для многочлена f (x ).

4. Если окажется, что g (x ) = 1 или g (x ) = f (x ), следует перейти к шагу 1 и, выбрав новое значение d , продолжить выполнение алгоритма.

Количество операций на шаге 2 оценивается величиной O (lnp ), если вычисления проводить так, как это указывалось выше при нахождении d (x ). Выясним теперь, сколь долго придётся выбирать числа d , пока на шаге 2 не будет найден собственный делитель f (x ).

Количество решений уравнения (t + a ₁ )^{( p – 1)/2} = (t + a ₂ )^{( p – 1)/2} в поле F_p не превосходит (p -3)/2. Это означает, что подмножество D ÌF_p , состоящее из элементов d , удовлетворяющих условиям

(d + a₁ )^{(p – 1)/ 2} ¹ (d + a₂ )^{(p – 1)/ 2} , d ¹ -a₁ , d ¹ -a₂ ,

состоит не менее чем (p – 1)/2 из элементов. Учитывая теперь, что каждый ненулевой элемент b ÎF_p удовлетворяет одному из равенств b ^{( p – 1)/2} = 1, либо b ^{( p – 1)/2} = –1, заключаем, что для d ÎD одно из чисел a₁ , a₂ будет корнем многочлена (x + d ) ^{( p – 1)/2} – 1, а другое – нет. Для таких элементов d многочлен, определённый на шаге 2 алгоритма, будет собственным делителем многочлена f (x ).

Итак, существует не менее (p –1)/2 «удачных» выборов элемента d , при которых на шаге 2 алгоритма многочлен f (x ) распадается на два собственных множителя. Следовательно, при «случайном» выборе элемента d Î F_p , вероятность того, что многочлен не разложится на множители после k повторений шагов алгоритма 1-4, не превосходит 2^-k . Вероятность с ростом k убывает очень быстро. И действительно, на практике этот алгоритм работает достаточно эффективно.

Заметим, что при оценке вероятности мы использовали только два корня многочлена f (x ). При n > 2 эта вероятность, конечно, ещё меньше. Более тонкий анализ с использованием оценок А. Вейля для сумм характеров показывает, что вероятность для многочлена f (x ) не распасться на множители при однократном проходе шагов алгоритма 1-4 не превосходит 2^-n + O (p ^-1/2 ). Здесь постоянная в O (.) зависит от n . В настоящее время известно элементарное доказательство оценки А. Вейля.

Если в сравнении (1) заменить простой модуль p составным модулем m , то задача нахождения решений соответствующего сравнения становится намного более сложной. Известные алгоритмы её решения основаны на сведении сравнения к совокупности сравнений (1) по простым модулям – делителям m , и, следовательно, они требуют разложения числа m на простые сомножители, что, как уже указывалось, является достаточно трудоёмкой задачей.

3.2 Произведение и возведение в степень многочленов, заданных массивами

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

type

Polynome =array [1..Nmax ] of Ring_Element ;

Следующий алгоритм даёт функцию умножения двух многочленов и , где многочлен степени (который даёт результат в конце алгоритма) должен быть предварительно инициализирован нулём.

for i := 0 to degP do

for j := 0 to degQ do

R [i +j ]:=R [i +j ]+P [i ]*Q [i ];

Изучая предыдущий алгоритм, устанавливаем, что его сложность как по числу перемножений, так и сложений, равна произведению высот двух многочленов: (degP + 1)(degQ + 1), но в этом алгоритме, который не учитывает случай нулевых коэффициентов, можно рассматривать высоту многочлена как число всех коэффициентов. Значит, возможно улучшить предыдущий алгоритм, исключив все ненужные перемножения:

for i := 0 to degP do

if P [i ] ¹ 0 then

for j := 0 to degQ do

if Q [j ] ¹ 0 then

R [i+j]:=R [i +j ]+P [i ]Q [i ];

Очень просто вычислить сложность алгоритма возведения в степень последовательными умножениями, если заметить, что когда P – многочлен степени d , то Pⁱ – многочлен степени id . Если обозначить C_mul (n ) сложность вычисления Pⁿ , то рекуррентное соотношение C_mul (i + 1) = C_mul (i ) + (d +1)(id +1) даёт нам:

C_mul (n ) = =

Что касается возведения в степень с помощью дихотомии (т.е. повторяющимися возведениями в квадрат), вычисления несколько сложнее: зная , вычисляем с мультипликативной сложностью. Как следствие имеем:

C _sqr (2^l ) = = =

=

Предварительное заключение, которое можно вывести из предыдущих вычислений, складывается в пользу дихотомического возведения в степень: если n есть степень двойки (гипотеза ad hoc), этот алгоритм ещё выдерживает конкуренцию, даже если эта победа гораздо скромнее в данном контексте (n ² d ² /3 против n ² d ² /2), чем когда работаем в Z/p Z (2log₂ n против n ).

Но мы не учли корректирующие перемножения, которые должны быть выполнены, когда показатель не является степенью двойки. Если n = 2l+1 – 1, нужно добавить к последовательным возведениям в квадрат перемножения всех полученных многочленов. Умножение многочлена степени (2ⁱ -1)d на многочлен степени 2ⁱ d вносит свой вклад из ((2ⁱ – 1)d + 1)( 2ⁱ d + 1) умножений, которые, будучи собранными по всем корректирующим вычислениям, дают дополнительную сложность:

= =

=

Теперь можно заключить, что дихотомическое возведение в степень не всегда является лучшим способом для вычисления степени многочлена с помощью перемножений многочленов. Число перемножений базисного кольца, которые необходимы, C _sqr (n ), - в действительности заключено между ( ) и т.е. между n ² d ² /3 и 2n ² d ² /3, тогда как простой алгоритм требует всегда n ² d ² /2 перемножений. В частности, если исходный многочлен имеет степень, большую или равную 4, возведение в степень наивным методом требует меньше перемножений в базисном кольце, чем бинарное возведение в степень, когда n имеет форму 2^l – 1.

Можно довольно просто доказать, что если n имеет вид 2^l +2^{l – 1} + c (выражения, представляющие двоичное разложение n ), то метод вычисления последовательными перемножениями лучше метода, использующего возведение в квадрат (этот последний метод требует корректирующего счёта ценой, по крайней мере, n ² d ² /9). Всё это доказывает, что наивный способ является лучшим для этого класса алгоритмов, по крайней мере, в половине случаев.

Действительно, МакКарти [3] доказал, что дихотомический алгоритм возведения в степень оптимален среди алгоритмов, оперирующих повторными умножениями, если действуют с плотными многочленами (антоним к разреженным) по модулю m , или с целыми и при условии оптимизации возведения в квадрат для сокращения его сложности наполовину (в этом случае сложность действительно падает приблизительно до n ² d ² /6 + n ² d ² /3 = n ² d ² /2).

3.3 Небольшие оптимизации для произведений многочленов

В принципе вычисление произведения двух многочленов степеней n и m соответственно требует (n +1)(m +1) элементарных перемножений. Алгоритм оптимизации возведения в квадрат состоит просто в применении формулы квадрата суммы:

что даёт n +1 умножений для первого члена и n (n +1)/2 – для второго, или в целом (n +1)(n +2)/2 умножений, что близко к половине предусмотренных умножений, когда n большое.

Для произведения двух многочленов первой степени P = aX +b иQ =cX + d достаточно легко находим формулы U =ac , W =bd , V = (a + b )(c + d ) и PQ = =UX ² + (V – U – W )X +W , в которых появляются только три элементарных умножения, но четыре сложения. Можно рекурсивно применить этот процесс для умножения двух многочленов P и Q степени 2^l – 1, представляя их в виде и применяя предыдущие формулы для вычисления PQ в зависимости от A , B , C и D , где каждое произведение AB , CD и (A + B )(C + D ) вычисляется с помощью рекурсивного применения данного метода (это метод Карацубы). Всё это даёт мультипликативную сложность M (2^l )и аддитивную сложность A (2^l )такие, что:

M (2^l ) = 3M (2^{l – 1} ),…, M (2) = 3M (1),M (1) = 1,

A (2^l ) =3A (2^{l – 1} ) + 3*2^l ,…, A (2) = 3A (1) + 6,A (1) = 1.

В этой последней формуле член 3*2^l представляет собой число элементарных сложений, необходимых, чтобы сделать два сложения многочленов степени 2^{l – 1} – 1 (a + b и c + d ) и два вычитания многочленов степени 2^l – 1 (U – V – W ). Суммируя каждое из этих выражений, находим для n , являющегося степенью двойки:

M (n ) = n ^log3/log2 »n ^1,585 иA (2) =7 n ^log3/log2 – 6n .

К сожалению, этот принцип остаётся теоретическим, и на его основе нужно построить итерационный алгоритм, чтобы получить разумную эффективность (цена управления рекурсией очень велика).

3.4 Вычисление многочленов

Рассмотрим общую задачу вычисления многочлена n -й степени

u (x ) = u_n xⁿ + u_{n – 1} x^{n – 1} + ... + u ₁ x + u ₀ , u_n ¹ 0, (1)

3.4.1 Схема Горнера

u (x ) = (…(u_n x + u_{n – 1} )x + …)x + u ₀ . (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 ):

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_n z + b_n ;

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

u (z ₀ ) = a_n z ₀ + 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 ) = a_n (x – x ₀ ) (x – x ₁ )…(x – x_{n – 1} ) +…+ a_n (x – x ₀ ) (x – x ₁ ) + a₁ (x – x ₀ ) + a₀ , (5)

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

u ^{[n ]} (x ) = ((…(a_n (x – x_{n – 1} ) + a_{n – 1} )(x – x_{n – 2} ) + …)(x – x ₁ ) + a₁ )*

*(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^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 ).

Если , где все простые числа q_j малы, то указанная процедура позволяет найти вычеты x mod, i = 1,…,s , и, с помощью китайской теоремы об остатках, вычет x modp – 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 _s Log q _s º 1 (mod p – 1) (10)

и

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

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

Мы опишем ниже реализацию этой идеи, взятую из работы [1]. Эвристические соображения позволили авторам этой работы утверждать, что предложенный ими алгоритм требует L^{1 + e} , где L = , арифметических операций для вычисления Log b .

Положим

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

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

(H + c ₁ ) (H + c ₂ ) º J + (c ₁ + c ₂ )H + c ₁ c ₂ (mod p ). (12)

Если числа c_i не очень велики, скажем c_i £ L^{1/2 + e} при некотором e > 0, то правая часть сравнения (12) не превосходит p ^{1/2 + e /2} . Можно доказать, что случайно выбранное натуральное число x < p ^{1/2 + e /2} раскладывается в произведение простых чисел, меньших с вероятностью, большей, чем L^{-1/2 - e /2} .

Обозначим через S = {q ₁ ,…,q_s } совокупность всех простых чисел q < L^1/2 , а также всех простых чисел вида H + c при 0 < c < L^{1/2 + e} . Тогдаs = O (L^{1/2 + e} ). Будем теперь перебирать случайным образом числа и для каждой такой пары пытаться разложить на множители соответствующее выражение из правой части (12). Для разложения можно воспользоваться, например, делением на все простые числа, меньшие, чем L^1/2 . Перебрав все (L^{1/2 + e} )² /2 = O (L^{1 + 2 e} ) указанных пар с ¹ , с ² мы найдём, как это следует из указанных выше вероятностных соображений, не менее

L^{-1/2 - e /2} *O (L^{1 + 2 e} ) = O (L^{1/2 + 3 e /2} ) (13)

пар, для которых правая часть сравнения (12) полностью раскладывается на простые сомножители, меньшие L^1/2 . Сравнение (12), таким образом, принимает вид (8). Так строится система уравнений типа (9).

Напомним, что число а , согласно нашему предположению, существенно меньше, чем L^1/2 . Поэтому оно раскладывается в произведение простых чисел, входящих во множество {q ₁ ,…,q_s }, и это приводит к сравнению (10).

Заметим, что количество (13) найденных сравнений типа (9) превосходит число s . Следовательно, построенная система неоднородных линейных сравнений относительно Log q_i содержит сравнений больше, чем неизвестных. Конечно, множество её решений может при этом быть бесконечным. Одна из правдоподобных гипотез состоит в том, что система имеет всё-таки единственное решение, и, решив её, можно определить дискретные логарифмы всех чисел q_i . На этом завершается первый этап работы алгоритма из [1].

Как было отмечено, каждое из чисел, стоящих в правой части сравнения (12), не превосходит p ^{1/2 + e /2} . Поэтому оно раскладывается в произведение не более O (lnp ) простых сомножителей и, следовательно, каждое из сравнений (9) построенной системы содержит лишь O (lnp ) отличных от нуля коэффициентов. Матрица системы сравнений будет разреженной, что позволяет применять для её решения специальные методы с меньшей оценкой сложности, чем обычный гауссов метод исключения переменных.

Вместо перебора всех допустимых значений c_i в [1] предлагается использовать так называемое решето, отбрасывающее все пары этих чисел, для которых правая часть (12) заведомо не раскладывается в произведение малых простых сомножителей. Для каждого c₁ и каждой малой простой степени q ' < L^1/2 можно найти все решения c ² < L^1/2 линейного сравнения

J + (c ₁ + c ₂ )H + c ₁ c ₂ º 0 (mod q ').

Организованная правильным образом, эта процедура одновременно отбирает все нужные пары чисел c _1, c ₂ и даёт разложение на простые сомножители правых частей сравнений (12).

Итак, после первого этапа работы алгоритма в нашем распоряжении оказываются дискретные логарифмы всех чисел из множества S. Второй этап алгоритма сводит поиск дискретного логарифма числа b к поиску логарифмов некоторого множества чисел u , не превосходящих по величине L ² . Выбирая случайным образом число w не более L ^1/4 раз, можно, как показывают вероятностные соображения, найти такое w , что вычет a ^w b mod p раскладывается в произведение простых чисел, меньших L ² . Пусть

(mod p)

такое разложение, где u ₁ ,…,u_t – некоторые простые числа с условием L ^1/2 < u < < L ² . На поиск этого сравнения потребуется O (L^1/2 )арифметических операций. В результате вычисление дискретного логарифма числа b сводится к вычислению t дискретных логарифмов для чисел u_j , 1 £j £t среднего размера.

Наконец, на последнем этапе производится вычисление логарифмов всех чисел u_j . Пусть u – простое число из интервала условием L ^1/2 < u < L ² . Обозначим

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

Для любых целых чисел c ₁ , c ₂ < L ^{1/2 + e} выполняется сравнение

(H + c ₁ ) (H + c ₂ )u ºI + (c ₁ G+ c ₂ H + c ₁ c ₂ )u (mod p ). (14)

Отметим, что правая часть этого сравнения не превосходит p ^1/2 L ^{5/2 + e} . Просеивая все числа c ₁ , c ₂ из указанного интервала, можно найти такие, что числа G+ c ₂ и правая часть сравнения (14) состоят из простых сомножителей, не превосходящих L ^1/2 . Тогда сравнение (14) позволяет вычислить Log u . Вычисление Log b при известных уже значениях Log q₁ требует L ^{1/2 + e} арифметических операций.

Существуют и другие способы построения соотношений (8). В [2] для этого используются вычисления в полях алгебраических чисел. В качестве множителей в соотношения типа (8) используются не только простые числа, но и простые идеалы с небольшой нормой.

Задача вычисления дискретных логарифмов может рассматриваться также и в полях Fpⁿ , состоящих из pⁿ элементов, в мультипликативных группах классов вычетов (Z/m Z)*, в группах точек эллиптических кривых и вообще в произвольных группах.

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

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 xⁿ using elementary multiplication methods”, Math . Comp ., vol . 31, n ^o 137, 1977, pp . 251 – 256.