Сравнительный анализ вычислений с использованием сочетаний различных базисов конечных полей

Аннотация

Представлен сравнительный анализ сложности реализации алгоритмов обращения, возведения в степень в полях характеристики два, операции спаривания Тейта и финального экспоненцирования на суперсингулярной эллиптической кривой над такими полями с учетом возможности использования различных базисов конечных полей, в которых осуществляются вычисления. Используются полиномиальный базис (п.б.), поля, почти п.б, оптимальный нормальный базис (о.н.б.) и переставленный о.н.б. (п.о.н.б.) базис поля, генератор о.н.б. 2-го или 3-го типа, а также удвоенный п.п.б., и удвоенный п.о.н.б., преобразования этих базисов. Используется операция умножения, реализованная последовательной программой умножения по алгоритму Карацубы. С использованием этих базисов и операции рассмотрены операции умножения, обращения в возведения в степень). Показано, что возведение в степень для обращения по малой теореме Ферма можно осуществить, используя 12 умножений при ничтожных затратах на возведения в квадрат. Но обращение с использованием модификации расширенного алгоритма Евклида требует существенно меньших элементарных операций ⊕ ,& и битовых присваиваний и даже только логических операций по равнению с экспоненцированием по Ферма, что подтверждается усредненными данными по 100 исполнениям операции обращения. Операции спаривания и финального экспоненцирования выполняются в расширении 4-й степени поля с использованием его п.б. или о.н.б. 1-го типа при п.б., п.п.б. или п.о.н.б. исходного поля. Показано, что при использовании для умножения многочленов степени 190 в кольце последовательной программой по методу Карацубы в криптографически значимом поле для спаривания наилучшее сочетание составляют п.о.н.б. поля и п.б. его расширения. При умножении по рекордной по числу исполняемых логических операций программе более предпочтительным является сочетание п.б. основного поля и о.н.б. 1-го типа его расширения. Однако существенное преимущество финального экспоненцирования в п.о.н.б. основного поля и о.н.б. 1-го типа его расширения влечет преимущество использования этого базиса основного поля как при спаривании, так и при финальном экспоненцировании, а для эффективной реализации следующего после операции спаривания операции финального экспоненцирования необходимо преобразование из п.б. в о.н.б. расширения поля, что реализуется просто при использовании общего для п.б. и о.н.б. минимального многочлена. Тогда финальное экспоненцирование осуществляется 17-ю умножениями в расширении поля при практически ничтожных затратах на возведения в квадрат в промежуточных вычислениях. Результаты получены на основе анализа первоисточников, алгоритмов и посредством компьютерных экспериментов.