Многочлен, в котором все коэффициенты равны единице
В математике многочлен из всех единиц (AOP) — это многочлен , все коэффициенты которого равны единице. Над конечным полем порядка два известны условия неприводимости AOP , которые позволяют использовать этот многочлен для определения эффективных алгоритмов и схем для умножения в конечных полях характеристики два . [1] AOP — это 1- равномерно распределенный многочлен . [2]
Определение
АОП степени m имеет все члены от x m до x 0 с коэффициентами 1 и может быть записана как
или
или
Таким образом, корни многочлена степени m, состоящего из одного числа , являются всеми корнями ( m +1)-й степени из единицы, отличными от самой единицы.
Характеристики
Над GF(2) АОП имеет много интересных свойств, в том числе:
Несмотря на то, что вес Хэмминга велик, из-за простоты представления и других улучшений существуют эффективные реализации в таких областях, как теория кодирования и криптография . [1]
Над , AOP неприводим, когда m + 1 является простым числом p , и, следовательно, в этих случаях p -й циклотомический многочлен . [4]
Ссылки
- ^ abc Коэн, Анри; Фрей, Герхард; Аванци, Роберто; Дош, Кристоф; Ланге, Таня ; Нгуен, Ким; Веркотерен, Фредерик (2005), Справочник по криптографии на эллиптических и гиперэллиптичных кривых, Дискретная математика и ее приложения, CRC Press, стр. 215, ISBN 9781420034981.
- ^ Ито, Тошия; Цудзи, Шигео (1989), «Структура параллельных множителей для класса полей GF(2 m )», Информация и вычисления , 83 (1): 21–40, doi : 10.1016/0890-5401(89)90045-X.
- ^ Рейхани-Масолех, Араш; Хасан, М. Анвар (2003), «О низкосложных параллельных битовых полиномиальных базисных множителях», Криптографическое оборудование и встраиваемые системы — CHES 2003 , Lecture Notes in Computer Science, т. 2779, Springer, стр. 189–202, doi : 10.1007/978-3-540-45238-6_16.
- ^ Сугимура, Тацуо; Суетугу, Ясунори (1991), «Соображения о неприводимых циклотомических многочленах», Электроника и связь в Японии , 74 (4): 106–113, doi :10.1002/ecjc.4430740412, MR 1136200.
Внешние ссылки