Оглавление
Введение
Глава 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 Выводы.
Заключение.
Библиографический список.
Приложения.
Введение
В работе рассматривается актуальная задача повышения эффективности реализации алгебраических операций в конечных алгебраических структурах. Она имеет существенное значение в информационных технологиях, в частности в обеспечении быстродействия систем цифровой обработки сигналов и криптографических протоколов. Этой задаче посвящено значительное количество как теоретических работ, так и работ практической направленности.
Можно считать, что изучение асимптотически быстрых алгоритмов умножения началось еще до появления понятия криптографии с открытым ключом, в. году, когда А. Карацуба предложил использовать метод
умножения, имеющий асимптотическую сложность О я 3 . Несколько позднее, Тоомом и Куком в г. в работах Г и было показано,
что данную асимптотическую оценку можно улучшить, до i22i 2 я. А в году в работах , был предложен метод умножения, использующий быстрое дискретное преобразование Фурье и показано, что он имеет асимптотическую сложность 0п 2 п 2 2.
Изучение операции инвертирования в поле началось намного позднее и нашло свое отражение в работах И, , , , , . В работах И, , рассматриваются алгоритмы инвертирования, использующее следствие из малой теоремы Ферма, в , , , используются различные вариации расширенного алгоритма Евклида, имеющего асимптотическую сложность он3, а в был предложен более эффективный вариант расширенного алгоритма, однако известен теоретически более быстрый вариант ШенхагеМоенка алгоритма Евклида, его асимптотическая сложность оценивается как 0iI где Мп сложность умножения многочленов степени п , . В работе в году алгоритмы инвертирования в бинарных полях были обобщены на поля характеристики большей или равной трех.
Актуальность
- Київ+380960830922