Научный руководитель – , д. т.н., профессор

Московский Энергетический Институт

(технический университет)

Автоматизация процесса синтеза схем умножения многочленов над полем Галуа GF(2) на базе метода Карацубы.

  В последние годы бурно развивается криптография с от-крытым ключом, ее теория и практические задачи [1]. При реализации криптографических протоколов приходится иметь дело с бинарными многочленами высоких степеней (порядка 102-105). В связи с этим, задача оптимизации операции умножения таких полиномов становится весьма актуальной. Один из подходов к данной задаче – применение метода Карацубы [2]. Этот метод позволяет свести умножение двух 2n-значных чисел к трём умножениям n-значных чисел. Применительно к полям Галуа GF(2), данный метод дает возможность свести операцию умножения двух полиномов степени 2n к трем умножениям полиномов степени n. Вполне естественно применять данный метод и к получаемым сомножителям до тех пор, пока степень сомножителей не станет такой, для которой умножение можно выполнить более эффективно [3]. Многочлены такой степени назовем элементарными.  (Например, для многочленов степени не выше 7 удобно выполнять умножение по заранее вычисляемой таблице). Однако, оптимизацию данного алгоритма можно продолжить, раскрывая рекурсию и создавая прямые схемы умножения. Примеры подобных схем приведены в работе [3].

В данной работе предлагается метод автоматиза-ции построения таких схем при заданных степенях много-членов базисных преобразований и порядках степеней со-множителей. При раскрытии рекурсии фактически получа-ется набор сумм произведений элементарных многочленов, задающий искомое произведение. При этом, выделяются повторяющиеся суммы для предотвращения дублирования их вычислений. Таким образом, сокращается количество операций сложения многочленов по сравнению с рекурсив-ным алгоритмом.  Используя свойства поля Галуа GF(2), можно также избавиться и от избыточных сложений одина-ковых многочленов. Важно заметить, что получаемая схема умножения не зависит от степени элементарных многочленов. 

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

Сравнительный анализ скорости работы алгорит-мов приведен в таблице.


Степень операндов

Классический алгоритм умножения

Рекурсивный алгоритм Карацубы

Синтезированные прямые схемы умножения

127

0.35

0.083

0.05

191

0.76

0.277

0.15

255

1.28

0.286

0.19

511

4.56

1.015

0.69

1023

17.18

3.141

2.32

Время работы указано в секундах, эксперименты проводи-лись на компьютере с процессором INTEL Pentium III - 450.

Литература:


риптография с открытым ключом М.: Мир 1996 г. , Умножение многозначных  чисел на автоматах // ДАН СССР. 1962. 145 №2. с.293-294. , , Программные и схемные методы  умножения многочленов для эллиптической криптографии  // Известия Академии Наук. Теория и системы управления. 2000г., № 5, с. 57-66.