Содержание к диссертации
Введение
Глава 1. Систематизация типичных алгоритмов в полях и кольцах 17
1.1 Наиболее распространенные алгоритмы умножения в кольце многочленов 19
1.1.1 Различные реализации метода сдвигов и сложений 19
1.1.2 Умножение с использованием метода Карацубы 26
1.1.3 Сравнение методов умножения 36
1.1.4 Наиболее распространенные алгоритмы приведения в кольце многочленов 38
1.2. Алгоритм возведения в степень 43
1.3. Алгоритмы инвертирования в стандартных базисах 44
1.4. Алгоритмы деления многочленов в поле 51
1.2 Выводы 55
Глава 2. Последовательные программы умножения и их синтез 57
2.1 Способы автоматического построения последовательных программ. 57
2.1.1 Аналитический способ построения последовательных программ...59
2.1.2 Рекурсивный алгоритм синтеза последовательной программы умножения многочленов 63
2.1.3 Автоматическое сравнение синтезированных последовательных программ умножения 65
2.2 Сравнение времени выполнения операции умножения для последовательных программ 72
2.2.1 Оценка для метода Карацубы с методом сдвигов и сложений, использующим таблицу умножения 74
2.2.2 Оценка для комбинации метода Карацубы и метода сдвигов и сложений с условными переходами 76
2.2.3 Оценка для метода Карацубы с использованием таблицы умножения 8-разрядных слов 80
2.3 Обобщение результатов на поля большой характеристики 83
2.4 Наилучшие алгоритмы, и границы их применимости 88
2.5 Выводы 93
Глава 3. Локализация адресов и циклическая реализация метода Карацубы 94
3.1 Локализация операндов и оптимизация метода по памяти 94
3.2 Оценка количества операций по перемещению и влияние модификации на выбор оптимального параметра 99
3.3 Циклическая реализация метода Карацубы 100
3.3.1 Общий анализ этапов, построение алгоритма 101
3.4 Сравнение времени умножения при использовании различных комбинированных методов 107
3.5 Выводы 114
Глава 4. Сравнительный анализ эффективности алгоритмов умножения точки эллиптической кривой на константу 115
4.1 Сложение и удвоение точек для суперсингулярной кривой над полем характеристики 2 116
4.1.1 Стандартный алгоритм сложения и удвоения 116
4.1.2 Алгоритм, использующий переход к проективным координатам. 116
4.1.3 Сравнение времени выполнения алгоритмов 119
4.2 Сложение и удвоение точек для несуперсингулярной кривой над полем характеристики 2 122
4.2.1 Стандартный алгоритм сложения и удвоения 122
4.2.2 Алгоритм, использующий переход к проективным координатам 122
4.2.3 Сравнение времени выполнения алгоритмов 125
4.3 Метод аддитивных цепочек для скалярного умножения точек
эллиптической кривой 128
4.4 Сравнение времени выполнения скалярного умножения точек эллиптических кривых различными алгоритмами 131
4.5 Выводы 136
Заключение 137
Библиографический список 139
Приложения 147
- Алгоритмы инвертирования в стандартных базисах
- Сравнение времени выполнения операции умножения для последовательных программ
- Оценка количества операций по перемещению и влияние модификации на выбор оптимального параметра
- Сравнение времени выполнения скалярного умножения точек эллиптических кривых различными алгоритмами
Введение к работе
В работе рассматривается актуальная задача повышения эффективности
реализации алгебраических операций в конечных алгебраических структурах. Она имеет существенное значение в информационных технологиях, в частности в обеспечении быстродействия систем цифровой обработки сигналов и криптографических протоколов. Этой задаче посвящено значительное количество как теоретических работ, так и работ практической направленности. Можно считать, что изучение асимптотически быстрых алгоритмов умножения началось еще до появления понятия криптографии с открытым ключом, в, 1962 году, когда А. Карацуба предложил использовать метод
умножения, имеющий асимптотическую сложность [33]. Несколько
позднее, Тоомом и Куком в 1963-1966 г. в работах [41] и [49] было показано,
что данную асимптотическую оценку можно улучшить, до О\п2^ ogz" 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] используются различные вариации расширенного алгоритма Евклида, имеющего асимптотическую сложность
0{п2), а в [44] был предложен более эффективный вариант расширенного алгоритма, однако известен теоретически более быстрый вариант Шенхаге-Моенка алгоритма Евклида, его асимптотическая сложность оценивается как 0(M(n)\og(ri)), где Ы(п) - сложность умножения многочленов степени п [72, 79]. В работе [20] в 2006 году алгоритмы инвертирования в бинарных полях были обобщены на поля характеристики большей или равной трех.
Актуальность темы. Понижение асимптотической сложности не всегда сопровождается понижением практической сложности, под которой мы понимаем число операций или время, затрачиваемые для выполнения операции при заданных размерностях операндов. Несмотря на сравнительно малую асимптотическую сложность изученных методов, при программной реализации в оценке сложности получается довольно большая мультипликативная константа, что существенно ограничивает целесообразность их применения на практике и делает актуальным исследование других, в том числе обладающих большей асимптотической сложностью методов, которые дают лучшие оценки производительности по времени для наиболее часто используемых в современных информационных системах размерностей операндов.
Не случайно на рубеже тысячелетий появились новые интерпретации давно известного метода сдвигов и сложений для реализации умножения [70], а также новые методы деления и инвертирования в конечных полях [81], имеющие лучшую производительность, чем асимптотически оптимальные методы в диапазоне размерностей современных криптографических протоколов.
Следует также отметить, что асимптотические оценки сложности схемной и программной реализации методов одинаковы и не учитывают той специфики последней, что производительность программы зависит от взаимного расположения операндов, а также от вспомогательных действий, связанных с организацией вычислений по программе (условных переходов, циклов). Чтобы сократить объем таких действий была предложена программная реализация метода Карацубы в виде декомпозиционной схемы, имеющей структуру ХПХХ
[И].
Для получения объективных оснований выбора того или иного метода при
реализации конкретной информационной системы необходимы разработка и
сравнительный анализ новых и известных методов (включая их
комбинирование) программной реализации алгебраических операций в тех или
иных диапазонах размерностей операндов, чему и посвящена тема настоящей
7 диссертации. Актуальность этой тематики проявляется и в бурном развитии эллиптической криптографии, где появились новые криптографические протоколы, не имеющие аналогов в классе протоколов, основанных на свойствах мультипликативной группы [7].
Целью диссертации является повышение эффективности программной реализации арифметических операций в конечных алгебраических структурах.
При этом ставились следующие задачи:
систематизация и программная реализация типичных алгоритмов в конечных алгебраических структурах;
разработка способов сравнения и оценки методов программной реализации алгебраических операций;
разработка методов автоматической генерации последовательных программ умножения;
сравнительный анализ и обоснование выбора методов программной реализации умножения в конечных полях;
сравнительный анализ и обоснование выбора методов программной реализации производных операций (возведения в степень, инвертирования и деления) в конечных полях;
сравнительный анализ методов программной реализации операций сложения и скалярного умножения в группе точек эллиптической кривой на основе рекомендуемых в диссертации методов умножения и деления в конечных полях.
Основные полученные в диссертации результаты:
1. Обоснована целесообразность комбинирования метода умножения путем сдвигов и сложений (вспомогательного метода) и метода Карацубы с уточнением порога перехода к вспомогательному методу умножения для комбинированных методов, построенных с использованием рекурсивной, циклической и последовательной реализации метода Карацубы.
Разработан метод автоматического синтеза последовательных программ умножения многочленов, обеспечивающий локализацию адресов, и способ автоматической верификации результата такого синтеза.
Разработан метод аналитического сравнения производительности последовательных программ умножения.
Определены наилучшие условия применения последовательных программ умножения по методу А. Карацубы в процессе умножения многочленов высоких степеней над полями различных характеристик и показано существенно большее быстродействие последовательных программ по сравнению с рекурсивными.
Выявлены области рекомендуемого применения методов при умножении многочленов высоких степеней над полями различных характеристик.
На основе сравнительного анализа эффективности алгоритмов скалярного умножения на эллиптических кривых с использованием аффинной и проективной систем представления операндов подтверждено, что существенное преимущество проективной системы сохраняется и в условиях применения наиболее эффективных алгоритмов умножения, инвертирования и деления в конечных полях.
Научная новизна полученных результатов:
Уточнен порог перехода для комбинированных методов, построенных с использованием рекурсивной, циклической и последовательной реализации метода Карацубы.
Предложен метод автоматического подтверждения правильности синтезируемых различными способами программ умножения.
Предложены аналитический метод оценки сложности и метод автоматического синтеза последовательных программ умножения по методу Карацубы, обеспечивающий локализацию адресов.
4. Подтверждена эффективность применения проективных координат при вычислениях в группе точек эллиптической кривой в условиях применения наиболее эффективных методов умножения и деления в конечных полях. Методы исследования. Поставленные задачи решались с использованием методов дискретной математики, линейной алгебры, теории вычислительной сложности алгоритмов. При разработке программного обеспечения использовались методы объектно-ориентированного программирования и техники оптимизации программного обеспечения.
Практическая значимость полученных результатов. Применение предложенного метода автоматической проверки правильности синтезированных программ позволит повысить качество разрабатываемого программного обеспечения и снизить временные затраты на его разработку и тестирование за счет формальной проверки 100% исходного кода еще до компиляции.
Полученные аналитическим и экспериментальным путями оценки и интервалы оптимальности методов умножения представляют практический интерес при программировании новых производных алгоритмов, использующих базовые операции.
Применение в алгоритмах на эллиптических кривых предложенных модификаций алгоритмов умножения в расширениях полей степени 256 и выше позволило сократить время выполнения операции умножения точки эллиптической кривой на константу на 5-15% в зависимости от типа кривой. Реализация результатов. Работа выполнялась в соответствии с проектом РФФИ 08-01-00632-а и заданием по разработке программного средства «Алгебраический процессор» инновационной образовательной программы. Результаты внедрены в виде математического и методологического обеспечения лабораторной работы «Сравнительный анализ временных
10 характеристик алгоритмов операций в конечных группах, кольцах и полях» электронного образовательного ресурса «Алгебраический процессор» [43].
Апробация полученных результатов осуществлена при их обсуждении на одиннадцатой, двенадцатой,, четырнадцатой и пятнадцатой международных научно-технических конференциях студентов и аспирантов «Радиоэлектроника, электротехника и энергетика», Москва 2005, 2006, 2008, 2009; девятой, десятой и одиннадцатой Московских Международных телекоммуникационных конференциях студентов и молодых ученых «Молодежь и наука», Москва 2006, 2007, 2009.
Полученные результаты опубликованы в десяти печатных изданиях [23-31, 43], включая 3 статьи из перечня ВАК [23-25].
Основное содержание работы. Диссертация состоит из настоящего введения, четырех глав, заключения и библиографического списка.
Во введении обоснована актуальность темы диссертации, ее научная новизна и практическая значимость, сформулирована цель ' работы, рассматриваемые в ней задачи, и приведено краткое содержание диссертации по главам.
В первой главе рассмотрены известные алгоритмы выполнения базовых арифметических операций в конечных алгебраических структурах. Приводятся базовые определения и понятия, описано современное состояние проблемы, а также идеи использования комбинированных алгоритмов и дается постановка задачи.
Во второй главе обосновывается способ автоматического построения последовательных программ умножения и для последовательных программ, построенных по комбинированному методу, приводится метод выбора оптимального параметра - размерности базы рекурсии, осуществляемой при синтезе программы.
Идея схемной реализации метода Карацубы была предложена и обоснована в 1999-2006 г.г. в работах [4, 5] и заключается в том, что предварительное сложение и умножение фрагментов многочленов, как и последующая сборка этих результатов, осуществляется схемой без циклов. Автоматизация построения таких схем была рассмотрена в работах [22, 42]. В обеих работах на основе аналитического исследования метода строились таблицы операций и адресов операндов, а затем из таких таблиц извлекалась схема. Однако такой метод построения схем не учитывает необходимость оптимизации по объему занимаемой памяти и по размещению в ней результатов промежуточных вычислений, что делает его применение довольно ограниченным для получения последовательных программ умножения. В нашем случае под последовательной программой понимается последовательность элементарных арифметических действий и операций присваивания. Последовательная программа характеризуется размером этой последовательности, объемом используемой памяти и степенью локализации адресаций. По этим параметрам последовательные программы можно оптимизировать.
Важной особенностью таких последовательных программ является независимость хода выполнения от исходных данных. Эта особенность позволяет путем несложных преобразований, для каждого разряда многочлена - результата умножения, получить цепочку арифметических действий над разрядами операндов, производимых в процессе выполнения последовательной программы и приводящих к получению именно этого разряда результата. Такие цепочки не зависят от способов адресации, порядка выполнения не связанных между собой операций и задают математическую суть программы. Значит, в случае эквивалентности двух программ будут порождаться одинаковые цепочки действий по формированию разрядов результата умножения. Верно и обратное: в случае равенства цепочек действий программы эквивалентны.
12 Одним из способов автоматического построения последовательных программ умножения является использование аналитически выведенных формул и таблиц распределения адресов операндов в элементарных операциях.
Идея второго способа автоматического построения последовательного алгоритма заключается в использовании уже разработанной и проверенной рекурсивной программы умножения. В коде такой программы каждая операция выполнения элементарного действия заменяется операцией сохранения наименования действия и адресов операндов. Затем ищется минимальный адрес операнда и принимается за нулевой адрес рабочего массива последовательной программы, соответствующая поправка вносится во все адреса операндов. При данном подходе необходимо обоснование корректности получаемой в результате программы, поскольку сам подход содержит неочевидные преобразования.
Последовательные программы, получаемые в результате реализации описанных выше подходов, принадлежат одному классу, при этом отличаются только способами адресации элементов и методами распределения памяти для хранения- промежуточных результатов. Поэтому для доказательства их эквивалентности можно использовать метод сравнения цепочек действий. Таким образом, автоматизация проверки заключается в том, что при выбранных максимально возможных степенях сомножителей, задающих область применимости программ, автоматически синтезируются две последовательных программы с использованием первого подхода без оптимизации и второго подхода с оптимизацией. Затем из первой и второй программ извлекаются цепочки действий по формированию базовых слов результата умножения. Формальными преобразованиями производится автоматическое приведение цепочек к единому виду и их сравнение. При положительном заключении о равенстве цепочек формируется заключение о корректности обеих синтезированных программ.
13 В получаемых описанным выше методом последовательных программ умножения, можно выделить набор типовых операций, количество которых подчинено уточненной оценке:
Р = С^З1022"1 п2 + C23log2"' п2 + Същп2 + С^10*2"1 + С5щ + С6п2 + С7 (1)
Здесь ль «2 - параметры алгоритма, причем п = п{п2- количество разрядов в многочленах - операндах, а п2 - параметр перехода - размерность базы рекурсии, осуществляемой при синтезе программы. Таким образом, задача получения оценки сводится к задаче определения постоянных Сі,...,Су для ограниченного набора элементарных действий. Что делается путем построения семи последовательных программ и решением системы линейных уравнений для каждого выбранного действия. В итоге были получены следующие оценки:
1) для последовательных программ, построенных по комбинированному
методу, использующему метод сдвигов и сложений с таблицей
P = J*l*3l0^(rc 2)2+ — *3log2'"rc2- — *л +
256 V 2J 16 2 8 ;
+ 3log2'!l+4 ' (2)
2) для последовательных программ, построенных по комбинированному
методу, использующему метод сдвигов и сложений с условными
переходами
1 15^ 11
Р = — * 3log2ni щ + — * 3log2'h п2- — *п +
16 2 16 2 8
(3)
+ 36* З1022"1 +1
3) для последовательных программ, построенных по методу Карацубы, использующему таблицу умножения для многочленов степени не выше 7
14 (4)
Р = ±±!:*зІ082И-—*и + 4
243 8
Далее с использованием формул (2) и (3) функции сложности табулируются, и по таблицам определяется оптимальный параметр перехода для последовательных программ, построенных по комбинированным алгоритмам. В итоге было получено, что:
1) для последовательных программ, построенных по комбинированному
методу, использующему метод сдвигов и сложений с таблицей
оптимальный параметр перехода равен 32;
2) для последовательных программ, построенных по комбинированному
методу, использующему метод сдвигов и сложений с условными
переходами оптимальный параметр перехода равен 256.
Для обобщения данной оценки сложности операции умножения в GF(pn), где р>2, отмечается, что при реализации умножения над полями нечетной характеристики, возникает необходимость табулирования операций сложения и вычитания, для реализации которых в GF(2n) использовались операции «исключающего или» (XOR). То есть каждая операция «исключающего или» заменяется операциями адресации по таблицам сложения и вычитания в GF(p). Дополнительно с увеличением характеристики поля, последовательная программа неявно усложняется вследствие увеличения количества бинарных разрядов, которые отводятся на один элемент поля GF(p). Повторением вычислений констант, описанных выше, было получено, что функция сложности по количеству операций адресации в последовательной программе умножения многочленов в GF(3n) имеет вид:
р = 15*3log2'!lrc22 +107,5*З1062"1 л2 -106*fyi2 +12 Так как в указанной последовательной программе вместо всех арифметических операций использовались адресации по таблице, то для дальнейшего увеличения характеристики поля не требуется изменение алгоритма,
15 достаточно лишь заменить таблицы выполнения элементарных арифметических действий. Иначе, если обозначить S(w,p) - последовательную программу умножения многочленов степени п над полем GF(pn), то при условии использования таблиц операций с 8-разрядными словами и р<251,
получим S(n,2)=S((n/8)*L8/(Tlog2(p)l)J,p).
Полученная таким образом функция позволяет оценить сложность последовательной программы для любого значения параметра п и /?<251. А ограничение р<25\ определяется физическим ограничением машинной памяти на использование таблиц выполнения элементарных арифметических действий.
В третьей главе производится сравнение методов умножения по времени выполнения для колец многочленов и приводятся идеи оптимизации алгоритма за счет увеличения степени локализации промежуточных результатов вычислений.
Непосредственная реализация рекурсивного метода Карацубы при увеличении степени умножаемых многочленов влечет за собой значительное увеличение объема оперативной памяти, необходимой для хранения промежуточных результатов, что в свою очередь существенно увеличивает время, необходимое на выполнение операции умножения. Для минимизации затрат по памяти в работе предлагается модификация метода Карацубы, которая заключается во введении дополнительных операций по перемещению результатов вычисления таким образом, чтобы на каждом шаге метода перемножаемые многочлены располагались в оперативной памяти непосредственно друг за другом. Такое расположение позволяет записывать промежуточные результаты умножения многочленов меньшего порядка на место операндов, что исключает дублирование информации и позволяет более рационально использовать память за счет незначительного увеличения количества операций в алгоритме.
Т.к. данная модификация алгоритма не предполагает внесения изменений в арифметическую суть метода, то для проверки корректности реализации
операции умножения модифицированным методом используется способ сравнения цепочек арифметических действий, описанный в главе 2. Результаты экспериментов показали, что наибольший выигрыш по скорости дает последовательная реализация модифицированного алгоритма Карацубы, совмещенного с использующим таблицу методом сдвигов и сложений, с параметром перехода равным 32.
В четвертой главе проводится сравнительный анализ эффективности алгоритмов умножения точки эллиптической кривой на константу с использованием аффинной и проективной систем представления операндов и усовершенствованных алгоритмов умножения, инвертирования и деления в конечных полях. Результаты экспериментов подтверждают рекомендации по применению проективных координат: использование ускоренного расширенного алгоритма Евклида существенно сокращает время деления в диапазоне степеней, характерных для криптографического применения, что, однако, оказывается недостаточным для отказа от применения проективных координат для выполнения основных операций в группе точек эллиптической кривой, позволяющих сократить число делений за счет увеличения общего числа операций умножения. При этом применение оптимизированной операции умножения многочленов для выполнения операций над точками эллиптической кривой позволило сократить время умножения точки на константу на 5-15% в зависимости от типа кривой и порядка многочлена, образующего поле, в котором производятся вычисления. В заключении даны выводы по результатам исследования.
Алгоритмы инвертирования в стандартных базисах
Операции инвертирования и деления - это достаточно сложные, требующие значительных временных затрат операции, используемые в алгоритмах кодирования и защиты информации. Под операцией-деления в поле в данном случае подразумевается операция умножения на обратный элемент, т.е. А/В=А (В-1). Знаменательно то, что алгоритм деления без использования в явном виде умножения и инвертирования был предложен лишь в 2000 году [20]. Для выполнения инвертирования наиболее часто используются алгоритмы двух классов. Первый - алгоритмы, использующие следствие из малой теоремы Ферма о том, что Ар1=1 (mod р) для произвольного не равного нулю числа А и любого простого р (данная теорема без потери общности может быть переформулирована в термины поля многочленов). Второй класс состоит из алгоритмов, представляющих модификации расширенного алгоритма Евклида [59, 72, 78].
Данный алгоритм приводится в [20] со ссылкой на [81]. Алгоритм состоит из двух частей, в первой его части ищется так называемая «почти инверсия», то есть многочлен Ь, для которого выполняется равенство: b(x) a(x)=x (mod т(х)) при некотором фиксированном к. А во второй части производится коррекция результата, т.е. находится элемент d, для которого выполняется равенство d(x) a(x)=l (mod т(х)).
В табл. 1.3 приведены результаты сравнения времени выполнения операций инвертирования в полях характеристики 2. Так как время инвертирования сильно зависит от неприводимого многочлена, порождающего поле, измерения проводились для фиксированных трехчленов вида: l+xl+xm. В качестве многочлена для инвертирования выбиралось несколько случайных многочленов в поле, для каждого многочлена выполнялось инвертирование, а затем результаты измерения времени для каждой операции и набора инвертируемых многочленов усреднялись. Из табл. 1.3 видно, что наибольший выигрыш по времени обеспечивает использование почти инвертирующего алгоритма с последующей корректировкой результата.
Приведенные выше модификации алгоритма Евклида без значительных изменений могут быть использованы для выполнения операции деления в поле многочленов [44, 20]. Для этого на начальном шаге вместо присваивания dl:—l необходимо выполнить присваивание dl:=c. В результате на выходе алгоритма будет получен многочлен d, такой, что d b=c (mod т), т.е. d=c b ](mod т). Однако данная модификация не дает существенного преимущества по сравнению с классическим делением в поле (умножением на заранее инвертированный элемент), т.к. фактически производится лишь перенос одной операции умножения многочленов на первый цикл процедуры инвертирования. Соответствующие алгоритмы приведены на рис. 1.19 и рис. 1.20.
В табл. 1.4 приведены результаты сравнения времени деления в полях характеристики 2. Т.к. время инвертирования сильно зависит от неприводимого многочлена, порождающего поле, измерения проводились для фиксированных трехчленов вида: 1+х +хш. В качестве делимого и делителя выбиралось несколько случайных многочленов в поле, для каждой пары выполнялось деление, а затем результаты измерения времени для набора операндов и фиксированного многочлена, порождающего поле усреднялись. В табл. 1 А. использованы следующие методы: 1. Выполнялось инвертирование с помощью алгоритма Евклида (алгоритм 12), а затем умножение на делимое. 2. Выполнялось инвертирование с помощью модифицированного алгоритма Евклида, а затем умножение на делимое (алгоритм 13). 3. Выполнялось инвертирование с помощью почти инвертирующего алгоритма (алгоритмы 14 и 15), а затем умножение на делимое. 4. Использовался алгоритм 16. 5. Использовался алгоритм 17.
Из таблицы видно, что применение алгоритма деления, не использующего этапа умножения, вообще говоря, не дает существенного преимущества. Это связано с тем, что этап умножения на обратный элемент в алгоритмах 16 и 17 фактически переносится на первую итерацию алгоритма поиска обратного элемента (заметим, что в алгоритмах 12 и 13 умножение на первом цикле, при вычислении элемента d не выполнялось, т.к. один из множителей был равен 1).
Проведенные вычислительные эксперименты показали, что в случае умножения многочленов степени, меньшей 64, рекомендуется использовать метод сдвигов и сложений с таблицей умножения (алгоритм 2); для умножения многочленов степеней от 64 до 511 рекомендуется применять метод сдвигов и сложений с использованием таблицы определения единичных разрядов (алгоритм 4), а для умножения многочленов степеней, больших 511, лучшие результаты среди рассматриваемых алгоритмов дает комбинированный метод с таблицей определения единичных разрядов (алгоритм 6 и алгоритм 4) при параметре перехода 512. Очевидно, что использование рекурсивной реализации алгоритма Карацубы, несмотря на меньшую по сравнению с классическими методами асимптотическую сложность, не представляет практического интереса при малых степенях операндов. Это делает актуальной задачу исследования альтернативной реализации метода, которая рассматривается в главах 2 и 3. Меньшая асимптотическая сложность метода Карацубы говорит о том, что при увеличении степеней операндов использование данного метода становится более предпочтительным. Это, в свою очередь, делает целесообразным применение комбинированных методов умножения, в которых умножение многочленов степени п посредством выполнения log2(ni) шагов метода Карацубы сводится к некоторому количеству умножений многочленов степени п2 (n=ni n2), последние выполняются с использованием одного из классических методов сдвигов и сложений.
Сравнение времени выполнения операции умножения для последовательных программ
В данном разделе рассматривается один из возможных способов, позволяющий получить теоретическую оценку производительности и оптимальности выбранного метода без необходимости компиляции и выполнения конкретного алгоритма для выбранной сложности исходных данных. Так же в данном разделе рассматривается нахождение, на основе полученной оценки, оптимального соотношения параметров nhn2 для автоматически сгенерированных последовательных программ по комбинированному методу умножения.
Как было отмечено в главе 1, для комбинированного метода действительна следующая оценка сложности программы:
Эта формула позволяет сделать вывод о потенциальной возможности уменьшения времени выполнения умножения за счет комбинирования метода Карацубы и метода сдвигов и сложений, но для получения четкого ответа, эту оценку необходимо уточнять.
Выше в доказательстве формулы (1.1) при раскрытии сложности метода сдвигов и сложений 0(п2 ) учитывалась только старшая его составляющая. Для более точного представления необходимо считать 0(п2 )=СіП2 +С2п2+С3. Кроме того, при подсчете количества действий на этапе разложения по методу Карацубы в формуле сложности отбрасывался элемент младшего порядка CLn. В итоге получаем функцию, задающую сложность программной реализации метода: Далее для ответа на вопрос о выборе оптимальных параметров л; и и2 , при заданном п, необходимо определить константы, входящие в функцию сложности. Очевидным решением является проведение серии умножений с использованием этого метода для получения временных характеристик при различных значениях параметра и решение системы линейных уравнений. Но такой способ имеет ряд недостатков, наиболее значительным из которых является зависимость времени выполнения операции от производительности машины и количества процессов, запущенных на машине в момент проведения эксперимента, а так же невозможность измерить время точно. Поэтому встает вопрос об использовании объективной, не зависящей от среды проведения эксперимента оценки. В качестве такой оценки можно взять количество элементарных операций, используемых в последовательной программе умножения. Для этого в программе операции умножения методом сдвигов и сложений так же представляются в виде последовательности элементарных действий.
В составе такой программы можно выделить несколько типовых операций: 1) операция присваивания; 2) операция сложения по модулю 2; 3) операция наложения маски (логическое «И»); 4) операция битового сдвига; 5) операция адресации элемента в массиве.
Выполнение каждой из этих операций занимает определенное, вообще говоря, разное время, но поскольку все действия в последовательной программе производится с различными элементами рабочего массива, то каждая из операций сопровождается одной или несколькими операциями адресации. Поэтому при поиске оптимального соотношения параметров ttj и п.2 можно использовать число, характеризующее количество операций адресации.
Выберем один из алгоритмов умножения, например, комбинированный метод Карацубы с переходом к методу сдвигов и сложений, использующему таблицу умножения для вычисления произведений 8-разрядных машинных слов. Зафиксировав набор значений параметров п\,п2 можно построить таблицу значений функций, входящих в формулу для определения сложности и провести ряд построений последовательных программ для определения количества операций адресации, задействованных в последовательной программе.
Оценка количества операций по перемещению и влияние модификации на выбор оптимального параметра
Для оценки количества операций перемещения, вносимых в комбинированный алгоритм в процессе оптимизации по объему занимаемой памяти, напомним, что степень умножаемых многочленов А и В равна п-1, где n=ni n2, log2(ni) - количество итераций по методу Карацубы, а п2 - степень многочленов, умножаемых с помощью метода сдвигов и сложений. При этом на шаге і производится n/(2/3)1 = п(3/2) элементарных операций перемещения битов. Суммируя члены по формуле геометрической прогрессии, получим, что на весь метод добавится действий перемещения битов.
Например, если п=1024, а Пі=п2=32, то количество дополнительных перемещений для бинарных разрядов будет равно 2 32 243=15552. Учитывая, что перемещения выполняются базовыми словами (размер базового слова т=32), несложно подсчитать, что количество дополнительных операций перемещения базовых слов будет равно 486, что составляет не более 1% от общего числа операций в комбинированном методе с методом сдвигов и сложений с табличной реализацией, см. табл. 2.8.
Как известно, применение рекурсии в чистом виде зачастую не является оптимальным подходом, поскольку в рекурсивных алгоритмах присутствуют дополнительные операции передачи параметров в вызываемые функции и трудоемкие операции динамического выделения памяти под временные переменные, использования которых можно избежать, выполнив переход к циклической реализации алгоритма. В целях раскрытия рекурсии операция умножения разбивается на три этапа: 1. Прямой ход рекурсии - на каждом шаге этого этапа производятся вычисления слагаемых Q и подготовка слагаемых А и В к следующему шагу этого этапа. 2. Последний шаг прямого хода рекурсии - на этом этапе производится перемножение пар чисел, имеющих размер машинного слова. 3. Обратный ход рекурсии - на каждом шаге этого этапа производится сложение промежуточных результатов восстановление произведения двух чисел.
Как было отмечено выше, на каждом шаге этого этапа необходимо выполнять вычисление слагаемых С; и подготовку чисел А и В. Схематично шаги этого этапа изображены на рисунке 3.3. Оба многочлена А и В записываются в начало достаточно большой области памяти, затем из них выделяются старшие и младшие части и перемещаются в памяти таким образом, чтобы многочлены, которые необходимо перемножать на следующем шаге, находились в памяти последовательно. Аналогично располагаются и числа СІ в свободной области памяти. При этом сначала удобнее вычислять числа СІ (назовём эти действия правилом №1), а затем производить перемещение частей чисел А и В (назовём эти действия правилом №2).
Выполняя вычисления таким образом, на і-м шаге мы автоматически подготавливаем числа к і+1 шагу, который совершенно не отличается от предыдущего. Этап 2
Как только степень многочлена на некотором шаге этапа 1 достигает определённого значения, осуществляется переход к этапу 2, на котором производится перемножение многочленов. Вследствие введения специальных операций на первом этапе (правила 1 и 2), каждые два многочлена, которые необходимо перемножить, располагаются в памяти последовательно. Таким образом, на этом этапе нам необходимо произвести п og2 умножений для пар многочленов, расположенных в памяти последовательно, и записать результат умножения на место множителей. Этап 3
После выполнения этапа 2 мы получаем массив произведений, который может быть использован для обратного хода рекурсии. Арифметические действия этого этапа задаются формулой
Сравнение времени выполнения скалярного умножения точек эллиптических кривых различными алгоритмами
В табл. 4.5 приводятся результаты измерения времени выполнения операции умножения точки суперсингулярной эллиптической кривой на константу с использованием различных методов, рассмотренных в главе 4. В строках таблицы даны результаты измерения времени для следующих операций: 1 - умножение точки на константу выполнялось с использованием стандартного алгоритма сложения точек на несуперсингулярной эллиптической кривой с использованием для деления алгоритма Евклида, описанного в разделе 1.4.2; 2 - умножение точки на константу выполнялось с использованием стандартного алгоритма сложения точек на несуперсингулярной эллиптической кривой с использованием для деления модифицированного алгоритма Евклида, описанного в разделе 1.4.3; 3 - умножение точки на константу выполнялось с использованием стандартного алгоритма сложения точек на несуперсингулярной эллиптической кривой с использованием для деления почти инвертирующего алгоритма, описанного в разделе 1.4.4; умножение точки на константу выполнялось с использованием проективных координат, при этом время, затрачиваемое на действия по переходу в проективные координаты и обратно, не учитывалось.
В табл. 4.6 приводятся результаты измерения времени выполнения аналогичных операций умножения точки суперсингулярной кривой, но с использованием оптимизированных методов умножения многочленов, описанных в главах 2 и 3, для случаев, когда степень образующего многочлена, порождающего поле, в котором производились вычисления, больше 256. 1 - умножение точки на константу выполнялось с использованием стандартного алгоритма сложения точек на несуперсингулярной эллиптической кривой с использованием для деления алгоритма Евклида, описанного в разделе 1.4.2; 2- умножение точки на константу выполнялось с использованием стандартного алгоритма сложения точек на несуперсингулярной эллиптической кривой с использованием для деления модифицированного алгоритма Евклида, описанного в разделе 1.4.3; 3 - умножение точки на константу выполнялось с использованием стандартного алгоритма сложения точек на несуперсингулярной эллиптической кривой с использованием для деления почти инвертирующего алгоритма, описанного в разделе 1.4.4; умножение точки на константу выполнялось с использованием проективных координат, при этом время, затрачиваемое на действия по переходу в проективные координаты и обратно, не учитывалось. В строках таблицы даны результаты измерения времени для следующих операций: 1 - умножение точки на константу выполнялось с использованием стандартного алгоритма сложения точек на несуперсингулярнои эллиптической кривой с использованием для деления алгоритма Евклида, описанного в разделе 1.4.2; 2 - умножение точки на константу выполнялось с использованием стандартного алгоритма сложения точек на несуперсингулярнои эллиптической кривой с использованием для деления модифицированного алгоритма Евклида, описанного в разделе 1.4.3; 3 - умножение точки на константу выполнялось с использованием стандартного алгоритма сложения точек на несуперсингулярнои эллиптической кривой с использованием для деления почти инвертирующего алгоритма, описанного в разделе 1.4.4; умножение точки на константу выполнялось с использованием проективных координат, при этом время, затрачиваемое на действия по переходу в проективные координаты и обратно, не учитывалось.
В табл. 4.8 приводятся результаты измерения времени выполнения аналогичных операций умножения точки несуперсингулярной кривой, но с использованием оптимизированных методов умножения многочленов, описанных в главах 2 и 3, для случаев, когда степень образующего многочлена, порождающего поле, в котором производились вычисления, больше 256. В строках таблицы даны результаты измерения времени для следующих операций: умножение точки на константу выполнялось с использованием стандартного алгоритма сложения точек на несуперсингулярной эллиптической кривой с использованием для деления алгоритма Евклида, описанного в разделе 1.4.2; 2- умножение точки на константу выполнялось с использованием стандартного алгоритма сложения точек на несуперсингулярной эллиптической кривой с использованием для деления модифицированного алгоритма Евклида, описанного в разделе 1.4.3; 3 - умножение точки на константу выполнялось с использованием стандартного алгоритма сложения точек на несуперсингулярнои эллиптической кривой с использованием для деления почти инвертирующего алгоритма, описанного в разделе 1.4.4; 4 - умножение точки на константу выполнялось с использованием проективных координат, при этом время, затрачиваемое на действия по переходу в проективные координаты и обратно, не учитывалось.
