WikiDer > Полиномиальный базис

Polynomial basis

В математика, а полиномиальный базис это основа из кольцо многочленоврассматривается как векторное пространство над поле коэффициентов, или как бесплатный модуль над кольцо коэффициентов. Наиболее распространенным полиномиальным базисом является мономиальный базис состоящий из всех мономы. Другими полезными полиномиальными базисами являются Базис Бернштейна и различные последовательности ортогональные многочлены.

В случае конечное расширение из конечные поля, полиномиальный базис может также относиться к основа расширения формы

{ Displaystyle {1, альфа, ldots, альфа ^ {м-1} } ,,}

где α это корень примитивный многочлен степени м равна степени расширения.^[1]

Набор элементов GF (п^м) можно представить как:

{ displaystyle {0,1, alpha, alpha ^ {2}, ldots, alpha ^ {p ^ {m} -2} }}

с помощью Логарифмы Заха.

Дополнение

Сложение с использованием полиномиального базиса так же просто, как сложение по модулю п. Например, в GF (3^м):

{ Displaystyle (2 альфа ^ {2} +2 альфа +1) + (2 альфа +2) = 2 альфа ^ {2} +4 альфа + 3 = 2 альфа ^ {2} + альфа { pmod {3}}}

В GF (2^м), сложение особенно просто, поскольку сложение и вычитание по модулю 2 - это одно и то же (как и термины "отменить"), и, кроме того, эту операцию можно выполнить аппаратно, используя базовый XOR логический вентиль.

Умножение

Умножение двух элементов в полиномиальном базисе может быть выполнено обычным способом умножения, но есть несколько способов ускорить умножение, особенно аппаратно. Используя простой метод умножения двух элементов в GF (п^м) требуется до м² умножения в GF (п) и до м² − м дополнения в GF (п).

Некоторые из методов уменьшения этих значений включают:

Таблицы поиска - предварительно сохраненная таблица результатов; в основном используется для небольших полей, в противном случае таблица слишком велика для реализации
В Алгоритм Карацубы - многократное разбиение умножения на части, уменьшение общего количества умножений, но увеличение количества сложений. Как видно выше, сложение очень просто, но накладные расходы на разбиение и повторное объединение частей делают его непосильным для оборудования, хотя оно часто используется в программном обеспечении. Его можно использовать даже для общего умножения, и это делается во многих системы компьютерной алгебры.
Регистр сдвига с линейной обратной связьюумножение на основе
Подполе вычисления - нарушение умножения в GF (п^м) к умножениям в GF (п^Икс) и GF (п^у), где Икс × у = м. Это не часто используется в криптографических целях, так как некоторые составные поля степеней избегаются из-за известных атак на них.
Конвейерные множители - хранение промежуточных результатов в буферах, чтобы новые значения могли быть загружены в множитель быстрее
Систолические множители - использование множества клеток, которые общаются только с соседними клетками; как правило, систолические устройства используются для операций с интенсивными вычислениями, где размеры входных и выходных данных не так важны, например, умножение.

Квадрат

Возведение в квадрат - важная операция, поскольку ее можно использовать как для общего возведения в степень, так и для инверсии элемента. Самый простой способ возвести элемент в квадрат в полиномиальном базисе - это дважды применить выбранный алгоритм умножения к элементу. В общем случае можно сделать небольшие оптимизации, в частности, связанные с тем, что при умножении элемента на себя все биты будут одинаковыми. Однако на практике неприводимый многочлен поскольку поле выбрано с очень небольшим количеством ненулевых коэффициентов, что делает возведение в квадрат в полиномиальном базисе GF (2^м) намного проще, чем умножение.^[2]

Инверсия

Инверсию элементов можно выполнить разными способами, в том числе:

Таблицы поиска - опять же, только для небольших полей, иначе таблица будет слишком большой для реализации
Инверсия подполей - путем решения систем уравнений в подполях
Повторное возведение в квадрат и умножение - например, в GF (2^м), А⁻¹ = А^{2^м−2}
В Расширенный алгоритм Евклида
В Алгоритм инверсии Ито – Цуджи

Применение

Полиномиальный базис часто используется в криптографический приложения, основанные на задача дискретного логарифмирования такие как криптография на основе эллиптических кривых.

Преимущество полиномиального базиса в том, что умножение относительно легко. Напротив, нормальная основа является альтернативой полиномиальному базису и имеет более сложное умножение, но возведение в квадрат очень просто. Аппаратные реализации полиномиальной базисной арифметики обычно потребляют больше энергии, чем их обычные базисные аналоги.

использованная литература

^ Роман, Стивен (1995). Теория поля. Нью-Йорк: Springer-Verlag. ISBN 0-387-94407-9.
^ Хуапэн, Ву (2001). "О сложности возведения в квадрат полиномиального базиса в F (2^м)". Избранные области криптографии: 7-й ежегодный международный семинар, SAC 2000, Ватерлоо, Онтарио, Канада, 14–15 августа 2000 г.,. Springer. п. 118.

Смотрите также

[1] Роман, Стивен (1995). Теория поля. Нью-Йорк: Springer-Verlag. ISBN 0-387-94407-9.

[2] Хуапэн, Ву (2001). "О сложности возведения в квадрат полиномиального базиса в F (2^м)". Избранные области криптографии: 7-й ежегодный международный семинар, SAC 2000, Ватерлоо, Онтарио, Канада, 14–15 августа 2000 г.,. Springer. п. 118.

[1]

[2]

Navigation