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

• Автор: Жебет, Сергей Юрьевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 149 с. : ил.

Оглавление
Введение

Глава 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 Сложение и удвоение точек для суперсингулярной кривой над полем
характеристики
4.1.1 Стандартный алгоритм сложения и удвоения
4.1.2 Алгоритм, использующий переход к проективным координатам .
4.1.3 Сравнение времени выполнения алгоритмов
4.2 Сложение и удвоение точек для несуперсингулярной кривой над
полем характеристики
4.2.1 Стандартный алгоритм сложения и удвоения.
4.2.2 Алгоритм, использующий переход к проективным координатам .
4.2.3 Сравнение времени выполнения алгоритмов.
4.3 Метод аддитивных цепочек для скалярного умножения точек эллиптической кривой.
4.4 Сравнение времени выполнения скалярного умножения точек эллиптических кривых различными алгоритмами.
4.5 Выводы.
Заключение.
Библиографический список.
Приложения.
Введение
В работе рассматривается актуальная задача повышения эффективности реализации алгебраических операций в конечных алгебраических структурах. Она имеет существенное значение в информационных технологиях, в частности в обеспечении быстродействия систем цифровой обработки сигналов и криптографических протоколов. Этой задаче посвящено значительное количество как теоретических работ, так и работ практической направленности.
Можно считать, что изучение асимптотически быстрых алгоритмов умножения началось еще до появления понятия криптографии с открытым ключом, в. году, когда А. Карацуба предложил использовать метод
умножения, имеющий асимптотическую сложность О я 3 . Несколько позднее, Тоомом и Куком в г. в работах Г и было показано,
что данную асимптотическую оценку можно улучшить, до ii 2 я. А в году в работах , был предложен метод умножения, использующий быстрое дискретное преобразование Фурье и показано, что он имеет асимптотическую сложность 0п 2 п 2 2.
Изучение операции инвертирования в поле началось намного позднее и нашло свое отражение в работах И, , , , , . В работах И, , рассматриваются алгоритмы инвертирования, использующее следствие из малой теоремы Ферма, в , , , используются различные вариации расширенного алгоритма Евклида, имеющего асимптотическую сложность он3, а в был предложен более эффективный вариант расширенного алгоритма, однако известен теоретически более быстрый вариант ШенхагеМоенка алгоритма Евклида, его асимптотическая сложность оценивается как 0iI где Мп сложность умножения многочленов степени п , . В работе в году алгоритмы инвертирования в бинарных полях были обобщены на поля характеристики большей или равной трех.
Актуальность


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