автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Исследование программных методов реализации операций в конечных алгебраических структурах

На правах рукописи

Жебет Сергей Юрьевич

Исследование программных методов реализации операций в конечных алгебраических структурах

Специальность: 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

ии34707Э4

Москва 2009

003470794

Работа выполнена на кафедре Математического моделирования Московского энергетического института (технического университета).

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

Фролов Александр Борисович.

Официальные оппоненты: доктор технических наук, профессор

Фальк Вадим Николаевич,

кандидат физико-математических наук, доцент Часовских Анатолий Александрович.

Ведущая организация: Федеральное государственное унитарное предприятие "НИИ "Квант".

Защита состоится «26» июня 2009 г. В 14:00 в ауд. М-704 на заседании диссертационного совета Д 212.157.01 при Московском энергетическом институте (техническом университете) по адресу: 111250, Москва, Красноказарменная ул., Д. 17.

С диссертацией можно ознакомиться в библиотеке Московского энергетического института (технического университета).

Отзывы в двух экземплярах, заверенные печатью организации, просьба отправлять по адресу: 111250, Москва, Красноказарменная ул., д.14, Ученый совет МЭИ (ТУ).

Автореферат разослан «££_» мая 2009 г.

Ученый секретарь

диссертационного совета Д 212.157.01 /

кандидат технических наук, доцент

Фомина М.В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Операции в конечных алгебраических структурах -кольцах, полях, группах, реализуемые в виде методов алгебраических библиотек, составляют вычислительную базу современных информационных технологий. Эффективность и надежность их реализации предопределяет соответствующие свойства таких информационных систем как системы цифровой обработки сигналов и криптографические протоколы. Вопросам эффективной реализации алгебраических операций посвящено значительное количество, как теоретических работ, так и работ практической направленности. В 1962 г. был опубликован метод умножения Карацубы1, как первый в понижении асимптотической оценки сложности целочисленного умножения. Затем был обоснован метод Шоенхаге-Штрассена2, понизивший эту оценку в еще большей степени. Однако понижение асимптотической сложности не всегда сопровождается понижением практической сложности, под которой мы понимаем число операций или время, затрачиваемые для выполнения операции при заданных размерностях операндов.

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

Не случайно на рубеже тысячелетий появились новые интерпретации давно известного метода сдвигов и сложений для реализации умножения3, а также новые методы деления и инвертирования в конечных полях4, имеющие лучшую производительность, чем асимптотически оптимальные методы в диапазоне размерностей современных криптографических протоколов.

Следует также отметить, что асимптотические оценки сложности схемной и программной реализации методов одинаковы и не учитывают той специфики последней, что производительность программы зависит от взаимного расположения операндов, а также от вспомогательных действий, связанных с организацией вычислений по про1рамме (условных переходов, циклов). Чтобы сократить объем таких действий была предложена программная реализация метода Карацубы в виде декомпозиционной схемы, имеющей структуру ЕП£Е5.

1 Каращ'ба A.A., Сфман Ю.П. Умножение многозначных чисел на автоматах // ДАН СССР. Т. 145 №2. 1962 с. 293-294.

2 Schönhage А., Strassen V. Schnelle Multiplikation grosser Zahlen. // Computing Wl 1971 p.281-292.

5 Lopez J., Dahab R. High Speed Multiplication in GF(2") // Proceedings of lndocrypt 2000, LNCS 1977. Springer, 2000. P.203-212.

4 Schrceppel R.s Orman H., Mallcy S'O., Spatschck O. Fast Key exchange with elliptic curve systems // CRYPTO 95, Lecture Notes in Computer Science. 1995 J*s 963. P. 43-56

5 Болотов A.A., Гашков С.Б., Фролов А.Б., Часовских A.A. О методах имплементации арифметических операций s криптографических системах // Известия РАН. Теория и системы управления. 2002 Jfel с 86-96. • V

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

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

При этом ставились следующие задачи:

1) систематизация и программная реализация типичных алгоритмов в конечных алгебраических структурах;

2) разработка способов сравнения и оценки методов программной реализации алгебраических операций;

3) разработка методов автоматической генерации последовательных программ умножения;

4) сравнительный анализ и обоснование выбора методов программной реализации умножения в конечных полях;

5) сравнительный анализ и обоснование выбора методов программной реализации производных операций (возведения в степень, инвертирования и деления) в конечных полях;

6) сравнительный анализ методов программной реализации операций сложения и скалярного умножения в группе точек эллиптической кривой на основе рекомендуемых в диссертации методов умножения и деления в конечных полях.

Полученные в диссертации научные результаты:

1. Обоснована целесообразность комбинирования метода умножения путем сдвигов и сложений (вспомогательного метода) и метода Карацубы с уточнением порога перехода к вспомогательному методу умножения для комбинированных методов, построенных с использованием рекурсивной, циклической и последовательной реализации метода Карацубы.

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

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

4. Определены наилучшие условия применения последовательных программ умножения по методу А. Карацубы в процессе умножения многочленов высоких степеней над полями различных характеристик и по-

6 A.A. Болотов, С.Б. Ггшков, А.Б. Фролов. Элементарное введение в эллиптическую криптографию. Протоколы криптографии на эллиптических кривых. - М.: Комкнига, 20G6.

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

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

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

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

Научная новизна:

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

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

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

4. Подтверждена эффективность применения проективных координат при вычислениях в группе точек эллиптической кривой в условиях применения наиболее эффективных методов умножения и деления в конечных полях.

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

Практическая значимость полученных результатов. Применение предложенного метода автоматической проверки правильности синтезированных программ умножения позволит повысить качество разрабатываемого программного обеспечения и снизить временные затраты на его разработку и тестирование за счет формальной проверки 100% исходного кода еще до компиляции.

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

Применение в алгоритмах на эллиптических кривых предложенных модификаций алгоритмов умножения многочленов для полей с порождающим многочленом степени больше 256 позволило сократить время выполнения операции умножения точки эллиптической кривой на константу на 5-15% в зависимости от типа кривой и порядка поля, в котором производились вычисления.

Реализация результатов. Работа выполнялась в соответствии с проектом РФФИ 08-01-00632-а и заданием по разработке про1раммного средства «Алгебраический процессор» инновационной образовательной программы. Разработанные программные средства использованы в МЭИ (ТУ) при создании электронного образовательного ресурса «Алгебраический процессор»'. Результаты внедрены в виде математического и методологического обеспечения лабораторной работы «Сравнительный анализ временных характеристик алгоритмов операций в конечных группах, кольцах и полях» электронного образовательного ресурса «Алгебраический процессор», и используются в лабораторном практикуме по дисциплине «Криптографические методы и средства защиты информации», что подтверждено актами об использовании.

Апробация полученных результатов осуществлена при их обсуждении на одиннадцатой, двенадцатой, четырнадцатой и пятнадцатой международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика», Москва 2005, 2006, 2008, 2009; девятой, десятой и одиннадцатой Московской Международной телекоммуникационной конференции студентов и молодых ученых «Молодежь и наука», Москва 2006, 2007, 2009.

Публикации. Основные результаты, полученные при выполнении диссертационной работы, опубликованы в 10 печатных изданиях, включая 3 статьи в журнале из Перечня ВАК.

Структура и объем работы. Работа состоит из введения, 4 глав, заключения, списка использованной литературы, содержащей 86 наименований, и приложений. Основной текст занимает 146 машинописных страниц, в том числе 31 . рисунок и 33 таблицы. Полный объем диссертации (с приложениями) составляет 149 страниц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность темы диссертации, ее научная новизна и практическая значимость, сформулирована цель работы и приведено краткое содержание диссертации по главам.

В первой главе приводятся базовые определения и понятия, описывается современное состояние проблемы, и рассматриваются известные алгоритмы выполнения арифметических операций в конечных кольцах и полях. При этом приводятся алгоритмы:

Фролов A.B. Алгебраический процессор [Электронный рес\рс]: для студентов и рспирантов всех специальностей АВТИ /А.Б.Фролов, С.Б. Гашксв, А-Ю.Белоза, С.Ю. Жебет, С.В.Морозов, А.В.Панхин, И.И. Щуров,. - М.: Издательский дом МЭИ, 2008.

1. Четыре вариации классического алгоритма умножения методом сдвигов и сложений.

2. Алгоритм умножения с использованием рекурсивной реализации метода Ка-рацубы.

3. Три комбинированных метода умножения (с использованием метода Кара-цубы и классического метода).

4. Два алгоритма приведения но модулю.

5. Алгоритм возведения в степень.

6. Четыре алгоритма инвертирования в поле в стандартном базисе.

7. Три алгоритма деления многочленов в поле в стандартном базисе.

Для каждого класса программ приводятся сравнительные таблицы времени выполнения и даются рекомендации по использованию одного из методов класса в зависимости от размера входных данных.

Для комбинированных методов умножения дополнительно приводится обоснование асимптотической оценки и производится экспериментальный выбор оптимальной базы рекурсии. Если представить количество разрядов в каждом многочлене множителе в виде п - и, * к,, где п2 - база рекурсии по методу Карацубы (количество разрядов в каждом многочлене - операнде, при котором производится переход от метода Карацубы к одном}' из вспомогательных методов), то глубина рекурсии по методу Карацубы определяется как 1о§2(иД при этом будет верно утверждение 1.

" го метода умножения асимптотическая

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

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

Идея схемной реализации метода Карацубы была предложена и обоснована в 1999-2006 г.г. в работах A.A. Болотова, С.Б. Гашкова, А.Б. Фролова и A.A. Часовских. Она заключается в том, что предварительное сложение и умножение фрагментов многочленов, как и последующая сборка этих результатов, осуществляется схемой без циклов. Автоматизация построения таких схем была рассмотрена в работах М.И. Фомичева и А.Б. Дроздова в 2001-2002 г.г. В обеих работах на основе аналитического исследования метода строятся таблицы операций и адресов операндов, а затем из таких таблиц извлекается схема. Однако такой метод построения схем не учитывает необходимость оптимизации по объему занимаемой памяти и по размещению в ней результатов промежуточ-

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

Мет[5]=Мет[1]; Мет[5]Л=Мет[2]; Мет [6]=Мет [4]; Мет[б]л=Мет[3];

.1/ЛЛ.М-Г.Г1 Мл^ГОП "1\.

1-1^! I пи"(.^/^-У/

Мет[3]=Ми1(Мет[2],Мегп[4],2);

Мет[5]=Ми!(Мет[5],МетГ6],2);

Мет[6]л=Мет[8];

Мет[5]л=Мет[7];

Мет[б]А=Мет[4];

МетГ5]л=Мет[3];

Мет[3]А=Мет[б];

Мет[8]л=Мет[5];

Мет[1]=Мет[7];

Мет[2]=Мет[8];_ __

Рнс. 1. Пример последовательной программы для умножения 64-разрядных бинарных

многочленов

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

Мет[1]=(А[0])*(В[0];[0]

МегГ|[2]=(А[О])*(Б[О])[1]+ГА[О]+А[1])*(В[1]+В[О])[О]+(А[0])*(ВГ0])ГО]+(А[1])*(В[1])[О] Мет[3]=(А[1])*(Б[1])[0]+(А[0]+А[1])*(В[1]+В[0])[1]+(А[0])*(В[0])[1]+(А[1])*(В[1])[1] МеФГ4НАГ»)*(ВГП)ГП______

Рис. 2. Пример цепочек действий для последовательной программы на рисунке 1

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

Одним из способов автоматического построения последовательных программ умножения является использование аналитически выведенных формул и таблиц распределения адресов операндов в элементарных операциях.

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

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

В получаемых описанным выше методом последовательных программ умножения, можно выделить набор типовых операций, количество которых подчинено уточненной оценке:

Р = С1З1"®2 Г,,п22 + С2 З1"82+ +Са З'08'"1 +С5я, +С6и2 +С7 0) Здесь П\, >ъ - параметры алгоритма, причем п = и, *пг- количество разрядов в многочленах - операндах. Эта формула едина для всех комбинированных методов, построенных на основе метода Карацубы и одной из реализаций метода сдвигов и сложений. Таким образом, задача получения оценки для конкретного комбинированного метода сводится к задаче определения постоянных Сь-.-.С?. Что делается путем построения семи последовательных программ и решением системы линейных уравнений относительно Сь...,С7. Например, соответствующая система уравнений для последовательных программ, построенных по комбинированному методу, использующему метод сдвигов и сложений с таблицей умножения, имеет вид:

а ее решение:

' 1024 32 32 1 1 32 1> ( 135

3072 96 64 3 32 1 | 441

12288 192 128 3 2 64 1 1 1619

36864 576 256 9 4 64 1 *С = 5025

110592 1728 512 27 8 64 1 15419

147456 1152 512 9 4 128 ! 18965

^248832 7776 1024 243 32 32 1 141121

С =

'_31_ 25 I256 16

■11 1 0 0 Л

задает коэффициенты в функции (1). В итоге были получены следующие оценки:

1) для последовательных программ, построенных по комбинированному методу, использующему метод сдвигов и сложений с таблицей (форму-ла(2));

2) для последовательных программ, построенных по комбинированному методу, использующему метод сдвигов и сложений с условными переходами (формула (3));

3) для последовательных программ, построенных по методу Карацубы, использующему таблицу умножения для многочленов степени не выше 7 (формула (4));

31

256 4 16

+ +4

11.

щ --

16

-36*3'°""' +!

251.

153 16

* З1^»] п ,

п.

'п +

11.

243 8

(2)

(3)

(4)

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

1) для последовательных программ, построенных по комбинированному методу, использующему метод сдвигов и сложений с таблицей оптимальный параметр перехода равен 32;

2) для последовательных программ, построенных по комбинированному методу, использующему метод сдвигов и сложений с условными переходами оптимальный параметр перехода равен 256;

Преимущество использования последовательных программ, построенных по комбинированным методам, перед рекурсивной реализацией метода Карацу-бы, комбинированных методов и классических алгоритмов при достаточно больших степенях умножаемых многочленов видно из табл. 1, полученной экспериментально8.

Табл. 1.

Результаты измерения времени выполнения операции умножения в С-Р(2") в микросекундах различными методами при задании оптимального параметра __для каждого метода.

Метод п<64 п<128 ! п<256 п<512 п<1024

Сдвигов и сложений с таблицей умножения 0,6 1,7 4,1 1 15 1 69

Метод сдвигов и сложений с использованием условных переходов 0,7 1,4 1 3,2 | 9,7 1 29

Метод сдвигов и сложений с использованием таблицы определения единичных разрядов 0,7 1,2 2,9 8,4 26

Метод Карацубы с таблицей умножения 1,5 4 | 12 35 130

Комбинированный метод с таблицей умножения (оптимальный параметр 256) 0,9 2 4 12 35

Комбинированный метод с использованием условных переходов (оптимальный параметр 512) 1 1,7 3,5 9,5 32

Комбинированный метод с таблицей определения единичных разрядов (оптимальный параметр 512) 0,9 1,4 3 9 25,5

Последовательный алгоритм по методу Карацубы с таблицей умножения 6,2 6,8 7,7 12 30

Последовательный алгоритм по комбинированному методу с таблицей умножения (оптимальный параметр 32) 6,1 6,7 1,2 8,3 12

Последовательный алгоритм по комбинированному методу с условными переходами (оптимальный параметр 256) 6,5 6,8 7,3 9,0 24 i

Для обобщения данных результатов на поля большой характеристики ОР(рг'), где 2<р<251, обозначим I - количество бинарных разрядов, которые не-

8 Здесь и далее все измерения времени выполнения алгоритмов проводились с использованием персонального компьютера со следующими характеристиками:

Процессор: tae! pentium4 2,S ГГц. Оперативная память: 5 ¡2 МБ. Операционная система: Windows ХР SP2. В промессе измерения времени было запушено только программное обеспечение, реализующее указанные алгоритмы.

обходимы для представления одного элемента поля ОР(р); т - количество бинарных разрядов в машинном слове; А: - количество элементов поля ОР(р), которые могут быть расположены в одном машинном слове. Тогда к=Ья//_].

При программировании операций умножения над такими полями, в качестве одного из вариантов реализации, можно использовать табулирование операций сложения и вычитания, для реализации которых в СР(2П) использовались операции «исключающего или» (Х(Ж), то есть каждая операция «исключающего или» заменяется операциями адресации по таблицам сложения и вычитания над СР(р"). Дополнительно с увеличением характеристики поля, последовательная программа неявно усложняется вследствие увеличения количества бинарных разрядов, которые отводятся на один элемент векторного представления элемента поля СР(рп). Повторением вычислений констант, описанных выше, было получено, что функция сложности в последовательной программе умножения многочленов над полем ОР(Зп) имеет вид:

Р = 15**„107,5*пг-Ш'

\*пг

+ 12

А оптимальный параметр перехода для такого метода будет равен 64. Так как в указанной последовательной программе вместо всех арифметических операций использовались адресации по таблице, то для дальнейшего увеличения характеристики поля не требуется изменение алгоритма, достаточно лишь заменить таблицы выполнения элементарных арифметических действий. Иначе, если обозначить Б(«,р) - последовательную программу умножения многочленов степени п над полем ОР(рп), то при условии использования таблиц операций с 8 разрядными словами и р<251, получим

Полученная таким образом функция, позволяет оценить сложность последовательной программы для любого значения параметра п и р<251. А ограничение р<251 определяется физическим ограничением машинной памяти на использование таблиц выполнения элементарных арифметических действий, как максимальное простое число, меньшее 256. Преимущество последовательных программ перед рекурсивным и классическим алгоритмом в полях большой характеристики видно из табл. 2.

Табл. 2.

Сравнительная таблица для операции умножения в ОРф") различными метода-

Метод ОР(р"), п/К6 4 64 <п/1 <128 ОР(рп), т<п.п <256 ОР(рп), 256<и/7 <512 СЖр0), 512 <п/1 <1024

Сдвигов и сложений с таблицей умножения 0,7 1,9 5 19 80

Метод Карацубы 1,9 5 ' ^ 13 45 150

Комбинированный метод (параметр перехода 64) - 2 4Д 13 37

Последовательный алгоритм по комбинированному методу (параметр перехода 64) 7,0 7,5 9,7 18

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

Непосредственная реализация рекурсивного метода Карацубы, при увеличении степени умножаемых многочленов, влечет за собой значительное увеличение объема оперативной памяти, необходимое для хранения промежуточных результатов, что в свою очередь увеличивает время, необходимое на выполнение операции умножения. Для минимизации затрат по памяти в работе предлагается модификация метода Карацубы, которая заключается во введении дополнительных операций но перемещению результатов вычисления таким образом, чтобы на каждом шаге метода перемножаемые многочлены располагались в оперативной памяти непосредственно друг за другом. Такое расположение позволяет записывать промежуточные результаты умножения многочленов меньшего порядка на место операндов, что исключает дублирование информации и позволяет более рационально использовать память за счет незначительного увеличения количества операций в алгоритме. В главе 3 также показывается, что количество дополнительных операций перемещения битов может быть вычислено по формуле:Р = 2л2л1'°ь!.

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

Из табл. 3 и 4, построенных по результатам экспериментов, видно, что наибольший выигрыш по скорости при достаточно больших степенях операндов дает последовательная реализация модифицированного алгоритма Карацубы, совмещенного с методом сдвигов и сложений с параметром перехода равным 32 для бинарных многочленов и 64 для обобщенного случая.

Табл. 3.

Результаты измерения времени выполнения операции умножения в ОР(2п) различными методами при задании оптимального параметра для каждого метода, ___время приводится в микросекундах. __

Метод п<64 п<128 п<256 п<512 п<1024

Сдвигов и сложений с таблицей умножения м 1,7 4,1 15 69

Метод сдвигов и сложений с использованием таблицы определения единичных разрядов 0,7 12 8,4 26

Продолжение табл. 3.

Метод Карацубы с таблицей умножения (рекурсивная реализация) 1,5 4 [ 12 35 130

Метод Карацубы с локализацией адресов и таблицей умножения (рекурсивная реализация) 1,4 3,9 11,7 34 127

Метод Карацубы с локализацией адресов и таблицей умножения (циклическая реализация) 1,4 3.8 11,5 33 125

Комбинированный метод с таблицей умножения (рекурсивная реализация, оптимальный параметр 256) 0,9 2 4 12 35

Комбинированный метод с локализацией адресов и таблицей умножения (рекурсивная реализация, оптимальный параметр 256) 0,9 2 4 12 34

Комбинированный метод Карацубы с локализацией адресов и таблицей умножения (циклическая реализация, оптимальный параметр 256) 0,9 2 4 10 31

Последовательный алгоритм по комбинированному методу с таблицей умножения (оптимальный параметр 32) 6,1 6,7 7,2 8,3 12

Последовательный алгоритм с локализацией адресов по комбинированному методу с таблицей умножения (оптимальный параметр 32) 6,1 6,6 7 11 И ~~ |

Табл. 4.

Сравнительная таблица для операции умножения в СР(рп) различными метода______ ми в микросекундах. __

Метод ОР(р"), п/1<64 ОР(рп), 64<п/1 <128 ОР(р°)г !28<п/1 <256 0Р(РИ), 256<п/1 <512 СР(рп), 512<п/1 <1024

Сдвигов и сложений с таблицей умножения М 5 19 80

Метод Карацубы (рекурсивная реализация) 1,9 5 13 45 150

Метод Карацубы с локализацией адресов (рекурсивная реализация) 1.7 5 12 44 145

Продолжение табл. 4,

Метод Карацубы с локализацией адресов (циклическая реализация) 1,7 5 12 43 142

Комбинированный метод (рекурсивная реализация, параметр перехода 64) - 2,0 4,1 13 37

Комбинированный метод с локализацией адресов (рекурсивная реализация, параметр перехода 64) - 2,0 4,0 12 35

Комбинированный метод с локализацией адресов (циклическая реализация, параметр перехода 64) - 1,9 19 11 9,7 32

Последовательный алгоритм по комбинированному методу (параметр перехода 64) 7,0 | 7,5 18

Последовательный алгоритм по комбинированному методу с локализацией адресов (параметр перехода 64) 7,0 7,3 М 12

В четвертой главе проводится сравнительный анализ эффективности алгоритмов сложения точек эллиптической кривой и умножения точки кривой на константу с использованием аффинной и проективной систем представления операндов и усовершенствованных алгоритмов умножения, инвертирования и деления в конечных полях. Указанные алгоритмы рассматриваются как для суперсингулярных, так и для несуперсингулярных эллиптических кривых. Результаты экспериментов подтверждают рекомендации по применению проективных координат для выполнения операций в группе точек суперсингулярной и несуперсингулярной эллиптических кривых. Хотя использование ускоренного расширенного алгоритма Евклида существенно сокращает время деления в диапазоне степеней, характерных для криптографического применения, этого охазывается недостаточно для отказа от применения проективных координат, позволяющих сократить число выполнений делений за счет увеличения общего числа операций умножения. При этом применение оптимизированной в главах 2 и 3 операции умножения многочленов для выполнения операций над точками эллиптической кривой позволило сократить время умножения точки на константу на 5-15% в зависимости от типа кривой и порядка многочлена, образующего поле, в котором производятся вычисления. В заключении даны выводы по результатам исследования.

В Приложениях приведены копии актов об использовании результатов диссертации.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Обоснована целесообразность комбинирования метода умножения путем сдвигов и сложений и метода Карацубы.

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

3. Определены наилучшие условия применения последовательных программ умножения по методу А. Карацубы в процессе умножения многочленов высоких степеней над полями различных характеристик.

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

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

6. Экспериментально подтверждены рекомендации по применению проективных координат в операциях умножения точки эллиптической кривой на константу.

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Жебет С.Ю. Сравнительный анализ алгоритмов умножения бинарных многочленов в полиномиальном базисе // Вестник МЭИ, №6,

2006, Москва, Издательство МЭИ, с. 52-61.

2. Жебет С.Ю. Сравнительный анализ алгоритмов умножения многочленов над полями большой характеристики // Вестник МЭИ, №6,

2007, Москва, Издательство МЭИ, с. 84-90.

3. Жебет С.Ю., Фролов А.Б. Автомагический синтез программ умножения многочленов над конечным полем // Вестник МЭИ, №6, 2008, Москва, Издательство МЭИ, с, 59-71.

4. Жебет С.Ю., рук. Фролов А.Б., д.т.н., проф. Автоматизация проверки программ умножения в кольцах многочленов над конечными полями // Радиоэлектроника, электротехника и энергетика. Тезисы докладов 15 Международной научно-технической конференции студентов и аспирантов в 3-х т. - М.: Издательство МЭИ, 2009, Т.1, с. 256-257.

5. Жебет С.Ю., рук. Фролов А.Б., д.т.н., проф. Автоматизация программирования операции умножения в кольцах многочленов над конечными полями // 12-я Московская международная телекоммуникационная конференция студентов и молодых ученых "Молодежь и наука" http://www.molod.mephi.ru/reports.asp?rid=6I2

6. Жебет С.Ю., рук. Фролов А.Б., д.т.н., проф. Анализ автоматически сгенерированных схем умножения полиномов по методу Карацубы // Радиоэлектроника, электротехника и энергетика. Тезисы докладов 12 Международной научно-технической конференции студентов и аспирантов в 3-х т. - М.: Издательство МЭИ, 2006, Т.1, с. 360-361.

7. Жебет С.Ю., рук. Фролов А.Б.. д.т.н., проф. Об одном методе оценки сложности алгоритма умножения многочленов над полем большой характеристики // Радиоэлектроника, электротехника и энергетика. Тезисы докладов 14 Международной научно-технической конференции студентов и аспирантов в 3-х т. - М.: Издательство МЭИ, 2008, Т. 1, с. 395-396.

8. Жебет С.Ю., рук. Фролов А.Б., д.т.н., проф. Об одном методе уточнения оценки сложности алгоритма (на примере алгоритма умножения в кольце многочленов) // Научная сессия МИФИ-2007. Конференция «Молодежь и наука». Сборник научных трудов. В 17 томах. - М.: МИФИ, 2007, т.16, с.

9. Жебет С.Ю., рук. Фролов А.Б., д.т.н., проф. Применение методов Фурье и Карацубы для оптимизации операции умножения полиномов .// Радиоэлектроника, электротехника и энергетика. Тезисы докладов 11 Международной научно-технической конференции студентов и аспирантов в 3-х т.-М.: Издательство МЭИ, 2005, Т.1, с. 303.

Ю.Фролов А.Б., Гашков С.Б., Белова А.Ю., Морозов C.B., Жебет С.Ю., Щуров И.И. Программное средство "Алгебраический процессор"// В кн. Информатизация инженерного образования: электронные образовательные ресурсы МЭИ. Выпуск 3 /' сост.: Ю.В.Арбузов, Т.И.Болдырева, А.И.Евсеев и др.; под общ. ред. С.И.Маслова. - М.: Издательский дом МЭИ, 2008. С.271-274.

110-111.

Подписано в печать Зак. />

Полиграфический центр МЭИ (ТУ) Красноказарменная ул., д13

Введение

Глава 1. Систематизация типичных алгоритмов в полях и кольцах.

1.1 Наиболее распространенные алгоритмы умножения в кольце многочленов.

1.1.1 Различные реализации метода сдвигов и сложений.

1.1.2 Умножение с использованием метода Карацубы.

1.1.3 Сравнение методов умножения.

1.1. Наиболее распространенные алгоритмы приведения в кольце многочленов.

1.2. Алгоритм возведения в степень.

1.3. Алгоритмы инвертирования в стандартных базисах.

1.4. Алгоритмы деления многочленов в поле.

1.2 Выводы.

Глава 2. Последовательные программы умножения и их синтез.

2.1 Способы автоматического построения последовательных программ.

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

2.1.2 Рекурсивный алгоритм синтеза последовательной программы умножения многочленов.

2.1.3 Автоматическое сравнение синтезированных последовательных программ умножения.

2.2 Сравнение времени выполнения операции умножения для последовательных программ.

2.2.1 Оценка для метода Карацубы с методом сдвигов и сложений, использующим таблицу умножения.

2.2.2 Оценка для комбинации метода Карацубы и метода сдвигов и сложений с условными переходами.

2.2.3 Оценка для метода Карацубы с использованием таблицы умножения 8-разрядных слов.

2.3 Обобщение результатов на поля большой характеристики.

2.4 Наилучшие алгоритмы, и границы их применимости.

2.5 Выводы.

Глава 3. Локализация адресов и циклическая реализация метода Карацубы

3.1 Локализация операндов и оптимизация метода по памяти.

3.2 Оценка количества операций по перемещению и влияние модификации на выбор оптимального параметра.

3.3 Циклическая реализация метода Карацубы.

3.3.1 Общий анализ этапов, построение алгоритма.

3.4 Сравнение времени умножения при использовании различных комбинированных методов.

3.5 Выводы.

Глава 4. Сравнительный анализ эффективности алгоритмов умножения точки эллиптической кривой на константу.

4.1 Сложение и удвоение точек для суперсингулярной кривой над полем характеристики 2.

4.1.1 Стандартный алгоритм сложения и удвоения.

4.1.2 Алгоритм, использующий переход к проективным координатам.

4.1.3 Сравнение времени выполнения алгоритмов.

4.2 Сложение и удвоение точек для несуперсингулярной кривой над полем характеристики 2.

4.2.1 Стандартный алгоритм сложения и удвоения.

4.2.2 Алгоритм, использующий переход к проективным координатам

4.2.3 Сравнение времени выполнения алгоритмов.

4.3 Метод аддитивных цепочек для скалярного умножения точек эллиптической кривой.

4.4 Сравнение времени выполнения скалярного умножения точек эллиптических кривых различными алгоритмами.

4.5 Выводы.

В работе рассматривается актуальная задача повышения эффективности реализации алгебраических операций в конечных алгебраических структурах. Она имеет существенное значение в информационных технологиях, в частности в обеспечении быстродействия систем цифровой обработки сигналов и криптографических протоколов. Этой задаче посвящено значительное количество как теоретических работ, так и работ практической направленности.

Можно считать, что изучение асимптотически быстрых алгоритмов умножения началось еще до появления понятия криптографии с открытым ключом, в, 1962 году, когда А. Карацуба предложил использовать метод умножения, имеющии асимптотическую сложность [33]. Несколько позднее, Тоомом и Куком в 1963-1966 г. в работах [41] и [49] было показано, что данную асимптотическую оценку можно улучшить, до oip.2^2log2" log2 nj. А в 1966-1971 году в работах [76, 78-80] был предложен- метод умножения, использующий быстрое дискретное преобразование Фурье и показано, что он имеет асимптотическую сложность 0(n\og2 n\og2 log2(n)).

Изучение операции инвертирования в поле началось намного позднее и нашло свое отражение в работах [11, 12, 20, 35, 65, 84]. В работах [11, 12, 65] рассматриваются алгоритмы инвертирования, использующее следствие из малой теоремы Ферма, в [35, 72, 79, 84] используются различные вариации расширенного алгоритма Евклида, имеющего асимптотическую сложность о(п3), а в [44] был предложен более эффективный вариант расширенного алгоритма, однако известен теоретически более быстрый вариант Шенхаге-Моенка алгоритма Евклида, его асимптотическая сложность оценивается как O(M(rc)log0z)), где М(и) - сложность умножения многочленов степени п [72, 79]. В работе [20] в 2006 году алгоритмы инвертирования в бинарных полях были обобщены на поля характеристики большей или равной трех.

Актуальность темы. Понижение асимптотической сложности не всегда сопровождается понижением практической сложности, под которой мы понимаем число операций или время, затрачиваемые для выполнения операции при заданных размерностях операндов. Несмотря на сравнительно малую асимптотическую сложность изученных методов, при программной реализации в оценке сложности получается довольно большая мультипликативная константа, что существенно ограничивает целесообразность их применения на практике и делает актуальным исследование других, в том числе обладающих большей асимптотической сложностью методов, которые дают лучшие оценки производительности по времени для наиболее часто используемых в современных информационных системах размерностей операндов.

Не случайно на рубеже тысячелетий появились новые интерпретации давно известного метода сдвигов и сложений для реализации умножения [70], а также новые методы деления и инвертирования в конечных полях [81], имеющие лучшую производительность, чем асимптотически оптимальные методы в диапазоне размерностей современных криптографических протоколов.

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

П].

Для получения объективных оснований выбора того или иного метода при реализации конкретной информационной системы необходимы разработка и сравнительный анализ новых и известных методов (включая их комбинирование) программной реализации алгебраических операций в тех или иных диапазонах размерностей операндов, чему и посвящена тема настоящей диссертации. Актуальность этой тематики проявляется и в бурном развитии эллиптической криптографии, где появились новые криптографические протоколы, не имеющие аналогов в классе протоколов, основанных на свойствах мультипликативной группы [7].

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

При этом ставились следующие задачи:

1) систематизация и программная реализация типичных алгоритмов в конечных алгебраических структурах;

2) разработка способов сравнения и оценки методов программной реализации алгебраических операций;

3) разработка методов автоматической генерации последовательных программ умножения;

4) сравнительный анализ и обоснование выбора методов программной реализации умножения в конечных полях;

5) сравнительный анализ и обоснование выбора методов программной реализации производных операций (возведения в степень, инвертирования и деления) в конечных полях;

6) сравнительный анализ методов программной реализации операций сложения и скалярного умножения в группе точек эллиптической кривой на основе рекомендуемых в диссертации методов умножения и деления в конечных полях.

Основные полученные в диссертации результаты:

1. Обоснована целесообразность комбинирования метода умножения путем сдвигов и сложений (вспомогательного метода) и метода Карацубы с уточнением порога перехода к вспомогательному методу умножения для комбинированных методов, построенных с использованием рекурсивной, циклической и последовательной реализации метода Карацубы.

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

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

4. Определены наилучшие условия применения последовательных программ умножения по методу А. Карацубы в процессе умножения многочленов высоких степеней над полями различных характеристик и показано существенно большее быстродействие последовательных программ по сравнению с рекурсивными.

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

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

Научная новизна полученных результатов:

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

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

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

4. Подтверждена эффективность применения проективных координат при вычислениях в группе точек эллиптической кривой в условиях применения наиболее эффективных методов умножения и деления в конечных полях.

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

Практическая значимость полученных результатов. Применение предложенного метода автоматической проверки правильности синтезированных программ позволит повысить качество разрабатываемого программного обеспечения и снизить временные затраты на его разработку и тестирование за счет формальной проверки 100% исходного кода еще до компиляции.

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

Применение в алгоритмах на эллиптических кривых предложенных модификаций алгоритмов умножения в расширениях полей степени 256 и выше позволило сократить время выполнения операции умножения точки эллиптической кривой на константу на 5-15% в зависимости от типа кривой. Реализация результатов. Работа выполнялась в соответствии с проектом РФФИ 08-01-00632-а и заданием по разработке программного средства «Алгебраический процессор» инновационной образовательной программы. Результаты внедрены в виде математического и методологического обеспечения лабораторной работы «Сравнительный анализ временных характеристик алгоритмов операций в конечных группах, кольцах и полях» электронного образовательного ресурса «Алгебраический процессор» [43].

Апробация полученных результатов осуществлена при их обсуждении на одиннадцатой, двенадцатой,. четырнадцатой и пятнадцатой международных научно-технических конференциях студентов и аспирантов «Радиоэлектроника, электротехника и энергетика», Москва 2005, 2006, 2008, 2009; девятой, десятой и одиннадцатой Московских Международных телекоммуникационных конференциях студентов и молодых ученых «Молодежь и наука», Москва 2006, 2007, 2009.

Полученные результаты опубликованы в десяти печатных изданиях [23-31, 43], включая 3 статьи из перечня ВАК [23-25].

Основное содержание работы. Диссертация состоит из настоящего введения, четырех глав, заключения и библиографического списка.

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

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

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

Идея схемной реализации метода Карацубы была предложена и обоснована в 1999-2006 г.г. в работах [4, 5] и заключается в том, что предварительное сложение и умножение фрагментов многочленов, как и последующая сборка этих результатов, осуществляется схемой без циклов. Автоматизация построения таких схем была рассмотрена в работах [22, 42]. В обеих работах на основе аналитического исследования метода строились таблицы операций и адресов операндов, а затем из таких таблиц извлекалась схема. Однако такой метод построения схем не учитывает необходимость оптимизации по объему занимаемой памяти и по размещению в ней результатов промежуточных вычислений, что делает его применение довольно ограниченным для получения последовательных программ умножения. В нашем случае под последовательной программой понимается последовательность элементарных арифметических действий и операций присваивания. Последовательная программа характеризуется размером этой последовательности, объемом используемой памяти и степенью локализации адресаций. По этим параметрам последовательные программы можно оптимизировать.

Важной особенностью таких последовательных программ является независимость хода выполнения от исходных данных. Эта особенность позволяет путем несложных преобразований, для каждого разряда многочлена - результата умножения, получить цепочку арифметических действий над разрядами операндов, производимых в процессе выполнения последовательной программы и приводящих к получению именно этого разряда результата. Такие цепочки не зависят от способов адресации, порядка выполнения не связанных между собой операций и задают математическую суть программы. Значит, в случае эквивалентности двух программ будут порождаться одинаковые цепочки действий по формированию разрядов результата умножения. Верно и обратное: в случае равенства цепочек действий программы эквивалентны.

Одним из способов автоматического построения последовательных программ умножения является использование аналитически выведенных формул и таблиц распределения адресов операндов в элементарных операциях.

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

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

В получаемых описанным выше методом последовательных программ умножения, можно выделить набор типовых операций, количество которых подчинено уточненной оценке:

Здесь ль П2 - параметры алгоритма, причем п = пхп2- количество разрядов в многочленах - операндах, а п2 - параметр перехода - размерность базы рекурсии, осуществляемой при синтезе программы. Таким образом, задача получения оценки сводится к задаче определения постоянных Сь.для ограниченного набора элементарных действий. Что делается путем построения семи последовательных программ и решением системы линейных уравнений для каждого выбранного действия. В итоге были получены следующие оценки:

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

2) для последовательных программ, построенных по комбинированному методу, использующему метод сдвигов и сложений с условными переходами

Р = С^З1022"1 п2 + С231оё2Щ п2 + Същп2 + С4 З1022"1 + С5пх + С6п2 + С7 С1) 310^'!1+4

1022 И,

2)

16 зб#з1о&"» +1

16 2 8

3)

3) для последовательных программ, построенных по методу Карацубы, использующему таблицу умножения для многочленов степени не выше 7

31оы.11*и + 4 ^

243 8

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

1) для последовательных программ, построенных по комбинированному методу, использующему метод сдвигов и сложений с таблицей оптимальный параметр перехода равен 32;

2) для последовательных программ, построенных по комбинированному методу, использующему метод сдвигов и сложений с условными переходами оптимальный параметр перехода равен 256.

Для обобщения данной оценки сложности операции умножения в СР(р"), где р>2, отмечается, что при реализации умножения над полями нечетной характеристики, возникает необходимость табулирования операций сложения и вычитания, для реализации которых в ОР(2п) использовались операции «исключающего или» (ХСЖ). То есть каждая операция «исключающего или» заменяется операциями адресации по таблицам сложения и вычитания в вР(р). Дополнительно с увеличением характеристики поля, последовательная программа неявно усложняется вследствие увеличения количества бинарных разрядов, которые отводятся на один элемент поля ОР(р). Повторением вычислений констант, описанных выше, было получено, что функция сложности по количеству операций адресации в последовательной программе умножения многочленов в СР(3П) имеет вид: р = 15 * З1^2"1 п22 +107,5 * З10®2"1 п2 -106 * щп2 +12 Так как в указанной последовательной программе вместо всех арифметических операций использовались адресации по таблице, то для дальнейшего увеличения характеристики поля не требуется изменение алгоритма, достаточно лишь заменить таблицы выполнения элементарных арифметических действий. Иначе, если обозначить 8(и,р) - последовательную программу умножения многочленов степени п над полем СР(рп), то при условии использования таблиц операций с 8-разрядными словами и р<251, получим 8(п,2)=8((п/8)4жГ^2(рЛ)-1,р).

Полученная таким образом функция позволяет оценить сложность последовательной программы для любого значения параметра п и р<251. А ограничение р<251 определяется физическим ограничением машинной памяти на использование таблиц выполнения элементарных арифметических действий.

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

Непосредственная реализация рекурсивного метода Карацубы при увеличении степени умножаемых многочленов влечет за собой значительное увеличение объема оперативной памяти, необходимой для хранения промежуточных результатов, что в свою очередь существенно увеличивает время, необходимое на выполнение операции умножения. Для минимизации затрат по памяти в работе предлагается модификация метода Карацубы, которая заключается во введении дополнительных операций по перемещению результатов вычисления таким образом, чтобы на каждом шаге метода перемножаемые многочлены располагались в оперативной памяти непосредственно друг за другом. Такое расположение позволяет записывать промежуточные результаты умножения многочленов меньшего порядка на место операндов, что исключает дублирование информации и позволяет более рационально использовать память за счет незначительного увеличения количества операций в алгоритме.

Т.к. данная модификация алгоритма не предполагает внесения изменений в арифметическую суть метода, то для проверки корректности реализации операции умножения модифицированным методом используется способ сравнения цепочек арифметических действий, описанный в главе 2. Результаты экспериментов показали, что наибольший выигрыш по скорости дает последовательная реализация модифицированного алгоритма Карацубы, совмещенного с использующим таблицу методом сдвигов и сложений, с параметром перехода равным 32.

В четвертой главе проводится сравнительный анализ эффективности алгоритмов умножения точки эллиптической кривой на константу с использованием аффинной и проективной систем представления операндов и усовершенствованных алгоритмов умножения, инвертирования и деления в конечных полях. Результаты экспериментов подтверждают рекомендации по применению проективных координат: использование ускоренного расширенного алгоритма Евклида существенно сокращает время деления в диапазоне степеней, характерных для криптографического применения, что, однако, оказывается недостаточным для отказа от применения проективных координат для выполнения основных операций в группе точек эллиптической кривой, позволяющих сократить число делений за счет увеличения общего числа операций умножения. При этом применение оптимизированной операции умножения многочленов для выполнения операций над точками эллиптической кривой позволило сократить время умножения точки на константу на 5-15% в зависимости от типа кривой и порядка многочлена, образующего поле, в котором производятся вычисления.

В заключении даны выводы по результатам исследования.

4.5 Выводы

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

Применение в алгоритмах на эллиптических кривых предложенных модификаций алгоритмов умножения в расширениях полей степени 256 и выше позволило сократить время выполнения операции умножения точки эллиптической кривой на константу на 5-15% в зависимости от типа кривой.

Заключение

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

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

3. Определены наилучшие условия применения последовательных программ умножения по методу А. Карацубы в процессе умножения многочленов высоких степеней над полями различных характеристик. Выбираемым параметром является глубина рекурсии при построении последовательной программы, она определяет ту максимальную степень многочленов, возникающих в процессе рекурсии, перемножение которых осуществляется одной из известных модификаций метода сдвигов и сложений, при достижении наилучшего алгоритма умножения этого типа в целом.

4. Произведено практическое сравнение методов умножения и инвертирования в поле многочленов, выявлены области рекомендуемого применения методов при умножении многочленов высоких степеней над полями различных характеристик.

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

6. Экспериментально подтверждены рекомендации по применению проективных координат в операциях умножения точки эллиптической кривой на константу.

7. В процессе выполнения работы была создана библиотека классов на языке С++, реализующая основные алгебраические функции в полях многочленов и на эллиптических кривых. В связи с использованием более низкого уровня языка программирования и неуправляемого кода разработанная библиотека показала пятикратное увеличение производительности по сравнению с существующим аналогом «Алгебраический процессор» на исходных данных, характерных для современной эллиптической криптографии.

1. Артемьева П.И., Фролов А.Б. О делении бинарных полиномов на полином с малым числом членов. // Вестник МЭИ, 2004 г., №6, стр. 5-16.

2. Ахо А., Хопкрофт Дж., Ульман Дж. «Построение и анализ вычислительных алгоритмов. // М.: Мир, 1979.

3. Бендерский Ю.В. Быстрые вычисления //ДАН СССР. 1975. Т. 223. № 5. С. 1041-1043.

4. Болотов A.A., Гашков С.Б., Фролов А.Б., Часовских A.A. Алгоритмические основы эллиптической криптографии. // Препринт. М.: МЭИ, 2000 г., 100 стр.

5. Болотов A.A., Гашков С.Б., Фролов А.Б., Часовских A.A. Программные и схемные методы умножения многочленов для эллиптической криптографии. // Известия Академии Наук. Теория и системы управления. 2000г. №5, стр. 66-75.

6. Болотов A.A., Гашков С.Б., Фролов А.Б., Часовских A.A. Элементарное введение в эллиптическую криптографию. Алгебраические и алгоритмические основы. М.: КомКнига, 2006, 324 стр.

7. Болотов A.A., Гашков С.Б., Фролов А.Б. Элементарное введение в эллиптическую криптографию. Протоколы криптографии на эллиптических кривых. М.: КомКнига, 2006, 274 стр.

8. Болотов A.A., Гашков С.Б. О быстром умножении в нормальных базисах конечных полей. // Дискретная математика, т.13 №3, 2001 г., стр. 3-31.

9. Болотов A.A., Гашков С.Б., Фролов А.Б. Криптографические протоколы на эллиптических кривых: учебное пособие по курсу «Криптографические методы защиты информации» М.: Издательский дом МЭИ, 2007. - 80 стр.

10. Болотов A.A., Гашков С.Б., Фролов А.Б. Криптографические протоколы, основанные на спаривании: учебное пособие по курсу «Криптографические методы защиты информации» М.: Издательский дом МЭИ, 2007. - 64 стр.

11. Болотов A.A., Гашков С.Б., Фролов А.Б., Часовских A.A. О методах имплементации арифметических операций в криптографических системах // Известия РАН. Теория и системы управления. 2002 №1 с 86-96.

12. Болотов A.A., Гашков С.Б., Фролов А.Б., Часовских A.A. О методах имплементации арифметических операций в полях Галуа // Вестник МЭИ. 2000 №4 с. 88-96.

13. Болотов A.A., Гашков С.Б., Фролов А.Б., Часовских A.A. О методах реализации умножения многочленов над конечными полями. Вестник МЭИ, №3, 2000 г., стр. 33-40.

14. Болотов A.A., Гашков С.Б., Хохлов P.A. Быстрые вычисления в конечных полях с использованием оптимальных, нормальных базисов. // Интеллектуальные системы, № 7 2002-2003 гг., стр 245-292.

15. Гашков С.Б. Замечания о быстром умножении многочленов, преобразовании Фурье и Хартли. // Дискретная математика, т. 12 № 3, 2000 г., стр. 124-153.

16. Гашков С.Б., Бурцев A.A. О схемах для арифметики в композитных полях большой характеристики. // Чебышевский сборник, т.7, вып.1, 2006 г., стр. 186204.

17. Гашков С.Б., Гашков И.Б., Бурцев A.A. О сложности булевых схем для арифметики в некоторых башнях конечных полей. // Вестник МГУ, Математика. Механика. № 5, 2006 г., стр. 10-16.

18. Гашков С.Б., Сергеев И.С. О приложении метода аддитивных цепочек к инвертированию в конечных полях. // Дискретная математика, № 4 2006 г., стр. 56-72.

19. Гашков С.Б., Фролов А.Б. Об умножении многочленов над конечным полем посредством быстрого преобразования Фурье. // Вестник МЭИ, №6, 2004 г., стр. 27-38.

20. Гашков С.Б., Фролов А.Б., Шилкин С.О. О некоторых алгоритмах инвертирования и деления в конечных кольцах и полях // Вестник МЭИ. 2006, №6, стр. 52-61.

21. Гашков С.Б., Хохлов P.A. О глубине логических схем для операций в конечных полях GF(2n). // Чебышевский сборник, т.4 №4(8), 2003 г., стр. 59-71.

22. Жебет С.Ю. Сравнительный анализ алгоритмов умножения бинарных многочленов в полиномиальном базисе // Вестник МЭИ, №6, 2006, Москва, Издательство МЭИ, с. 52-61.

23. Жебет С.Ю. Сравнительный анализ алгоритмов умножения многочленов над полями большой характеристики // Вестник МЭИ, №6, 2007, Москва, Издательство МЭИ, с. 84-90.

24. Жебет С.Ю. Фролов А.Б. Автоматический синтез программ умножения многочленов над конечным полем // Вестник МЭИ, №6, 2008, Москва, Издательство МЭИ, с. 59-71.

25. Карацуба А., Сложность вычислений. // Труды Математического института им. Стеклова, т. 211, с. 169-183 (1995).

26. Карацуба A.A., Офман Ю.П. Умножение многозначных чисел на автоматах// ДАН СССР. Т. 145 №2. 1962 с.293-294.

27. Касперски К. Техника оптимизации программ. Эффективное использование памяти СПб.: БХВ-Петербург, 2003. 464 с.

28. Кнут Д. Искусство программирования т.2 // СПб.: Вильяме, 2000

29. Лидл Р., Нидеррайтер Г. Конечные поля. М.: Мир, 1988 - 820 с.

30. Нечаев В.И. Элементы криптографии. М.: Высшая школа, 1999.

31. Саломаа А. Криптография с открытым ключом. М.: Мир, 1996.

32. Сергеев И.С. Инвертирование в конечных полях с логарифмической глубиной. //Математические вопросы кибернетики вып. 15 (2007), стр. 35-64.

33. Сергеев И.С. Об инвертировании в конечных полях характеристики два с логарифмической глубиной. // Вестник МГУ, Математика. Механика. № 1, 2007, стр.28-33.

34. Тоом A.JI. О сложности схемы из функциональных элементов, реализующей умножение целых чисел //ДАН СССР Т. 150 №3 1963 с. 496-498.

35. A1 US2002/0055962. Automatically solving equations in finite fields / Schroeppel R. // US Patent application №09/834, p.363

36. Ahmadi O., Menezes A. Irreducible polynomials of maximum weight. January 2005 Preprint. (http://www.cacr.math.uwaterloo.ca/~ajmeneze/publications/weightn.pdf)

37. Ash D.W., Blake I.F., Vanstone S.A. Low complexity normal bases //Discrete Applied Mathematics 1989. vol 25 p. 191-210.

38. Brent R., Gaudry P., Thome E., Zimmermann P. Faster multiplication in GF(2)x]. // Springer-Verlag, 2008, p. 153-166.

39. Brunner H., Curigerand A., Hofsteter M. On computing multiplicative inverses in GF(2n) // IEEE Transactionson Computers,Vol. 42, no.8 1993 p. 1010-1015

40. Cook S.A. On the Minimum Computation Time of Functions // Thesis, Harward University 1966 p. 51-77

41. Dahab R. Hankerson D., Hu F., Lang M., Lopez J., Menezes A. Software Multiplication using Normal Basis. 2005 (Technical report CACR 2004-12, University of Waterloo, 2004. http://cacr.math.uwaterloo.ca/ajmeneze).

42. Drolet G. A new representation of elements of finite fields GF(2m) yielding small complexity arithmetic circuits. // IEEE Transaction on Computers. 1998. 47. p.938-946

43. Fan H. and Hasan M.A., Alternative to the Karatsuba Algorithm for Software Implementation of GF(2n) Multiplication, Technical Report CACR 2006-13, Univ. of Waterloo, Waterloo, Canada, May 2006.

44. Fan H., Hasan M.A. A New Approach to Subquadratic Space Complexity Parallel Multipliers for Extended Binary Fields Technical Report CACR 2006-02, University of Waterloo, Jan:, 2006.

45. H. Fan and Y. Dai Fast bit parallel GF(2n) Multiplier for All Trinomials. //IEEE Transactions on Computers, vol. 54, no. 4, pp. 485-490, 2005.

46. Gantor D. On arithmetical algorithms over finite fields // Journal of Combinatorial Theory Series A, v.50 n.2, 1989, p.285-300

47. Gao S., Gathen J. von zur, Panario D. Gauss Periods: orders and cryptographical applications //Mathematics of Computation. 1998. vol. 67 p. 343-352.

48. Gao S., Lenstra H.W. Optimal normal bases // Design, Codes and Cryptography. 1992. vol. 2. p. 315-323.

49. Gao S., Vanstone S.A. On orders of optimal normal bases generators // Mathematics of Computation 1995. vol. 64 p. 1227-1233.

50. Gathen J. von zur, Gerhard J. Modern computer algebra. // Cambridge University Press 1999.

51. Gaudry, P., Kruppa, A., and Zimmermann, P. A GMP-based implementation of Schonhage-Strassen's large integer multiplication algorithm // Proceedings of ISSAC'07 (Waterloo, Ontario, Canada, 2007), pp. 167-174.

52. Geiselmann W., Lukhaub H. Redundant representation of finite fields. Public Key Cryptography // Lecture Notes in Computer Science 1992 №2001 p.339-352.

53. Granger R., Page D., Stam M. Hardware and software normal basis arithmetic for pairing based cryptography in characteristic three // IEEE Transaction on Computers v.54, No 7 (2005), 852-860.

54. Hankerson D., Lopez. J.H. Menezes A. Software implementation of elliptic curve cryptography over binary fields // CHES 2000, Lecture Notes in Computer Science. 2000. № 1965. p. 1-23.

55. Hankerson D., Menezes A., Vanstone S. Guide to Elliptic Curve Cryptography // Springer, 2004.

56. Itoh K., Takenaka M., Torii N. et. al. Fast implementation of public-key cryptography on DSP TMS320C6201, CHES'99, LNC 1717. 1999 p. 61-72

57. Jungnickel D. Finite fields: Structure and arithmetic. Wissenschaftsverlag, 1995.

58. Karacuba A., Berechnungen und die Kompliziertheit von Beziehungen. // EIK, N11, s. 10-12(1975).

59. Lim G.H., Lee P.G. More flexible exponentiation with precomputation. // Crypto-94. Springer p. 95-107

60. Lopez J. Dahab R. Improved algorithm for elliptic curve over GF(2n) SAC'98 // Lecture Notes in Computer Science 1999. № 1556 p.201-212.

61. Lopez J., Dahab R. High Speed Multiplication in GF(2m) // Proceedings of Indocrypt 2000, LNCS 1977. Springer, 2000. P.203-212

62. Menezes A, van P. Oorschot, Vanstone S. Handbook of Applied Cryptography. CRC Press. 1997.

63. Moenk R. Fast algorithm of GCD's // Proceedings of the 5th annual ACM Symposium on Theory of Computing. 1973. p. 142-151

64. Montgomery P. Five, Six, and Seven-Term Karatsuba-Like Formulae. // IEEE Transactions on Computers, vol. 54, no.3, 2005 p. 362-369,.

65. Montgomery P. Speeding the Polard and elliptic curve methods of factorization // Mathematics 5f-Computation. 1987. Vol. 48 p. 243-264.

66. Mullin. R.C., Onyszchuk I.M., Vanstone S.A., Wilson R.M. Optimal normal bases in GF(pn).

67. Pollard J.M. The fast Fourier transform in a finite field. Mathematics of Computation №25, 1971, 365-374

68. R. Katti and J. Brennan. Low complexity multiplication in a finite field using ring representation // IEEE Transactions on Computers, 52(4):418-427, 2003

69. Schonhage A. Schnelle berehnung von kettenbruchentwicklungen // Acta Informatica 1. 1971 p.139-144.

70. Schonhage A. Schnelle Multiplication von Polynomen über Koerpern der Charakteristik 2 // Acta Informatica. 1977 vol.7 p. 395-398

71. Schönhage A., Strassen V. Schnelle Multiplikation grosser Zahlen. // Computing №7 1971 p.281-292

72. Schroeppel R., Orman H., Malley S'O., Spatschek O. Fast Key exchange with elliptic curve systems // CRYPTO 95, Lecture Notes in Computer Science. 1995 № 963. p. 43-56

73. Shallit J. Origins of the Analysis of the Euclidean Algorithm. // Historia Mathematica, v. 21, pp. 401-419 (1994).

74. Silverman J.H. Fast Multiplication in Finite Fields GF(2N) // Cryptographic Hardware and Embedded Systems, Proc. First Intl Workshop, CHES 99, C K. Koc and C. Paar, eds. pp. 122-134, 1999.

75. Von zur Gathen J. Pappalardi F. On the reverse Artin problem for primitive roots // Preprint. 1995.

76. Wu H., Hasan M. A., Blake I.F., Gao S. Finite field multyplier using redundant representation // IEEE Transaction on Computers. 2002. 51. p/1306-1316.

77. Win E., Bosselaers A., Vandenberghe S., Gersem P., Vandewalle J. A fast software implementation for arithmetic operations in GF(2n) // Lecture Notes in Computer Science. Springer Berlin 1996 p. 65-76