Введение
Глава 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
