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

Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  «Полиномиальная основа»  -  новости  · газеты  · книги  · ученый  · JSTOR ( июнь 2014 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон ) Фактическая точность этой статьи оспаривается . Соответствующее обсуждение можно найти на странице обсуждения . Пожалуйста, помогите обеспечить надежный источник спорных заявлений . ( Июнь 2014 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

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

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

Тогда набор элементов GF ( p ^m ) можно представить в виде:

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

используя логарифмы Зеха .

Дополнение [ править ]

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

${\displaystyle (2\alpha ^{2}+2\alpha +1)+(2\alpha +2)=2\alpha ^{2}+4\alpha +3=2\alpha ^{2}+\alpha {\pmod {3}}}$

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

Умножение [ править ]

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

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

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

Квадрат [ править ]

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

Инверсия [ править ]

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

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

Использование [ править ]

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

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

Ссылки [ править ]

См. Также [ править ]

• Нормальная основа
• Двойная основа
• Смена основы