Все один многочлен - All one polynomial

An все один многочлен (АОП) - это многочлен в котором все коэффициенты равны единице. Над конечное поле второго порядка известны условия неприводимости АОП, которые позволяют использовать этот многочлен для определения эффективных алгоритмов и схем для умножение в конечные поля характеристики два.^[1] АОП - это 1-равноотстоящий многочлен.^[2]

Определение

AOP степени м имеет все условия от Икс^м к Икс⁰ с коэффициентами 1, и может быть записано как

${\displaystyle AOP_{m}(x)=\sum _{i=0}^{m}x^{i}}$

или

${\displaystyle AOP_{m}(x)=x^{m}+x^{m-1}+\cdots +x+1}$

или

${\displaystyle AOP_{m}(x)={x^{m+1}-1 \over {x-1}}.}$

Таким образом, корни все один многочлен степени м все (м+1) й корни единства кроме самого единства.

Характеристики

По сравнению с GF (2) АОП имеет много интересных свойств, в том числе:

• В Вес Хэмминга АОП м +1, максимально возможное для его степени^[3]
• АОП - это несводимый если и только если м + 1 простое и 2 простое первобытный корень по модулю м + 1^[1] (по GF (п) с штрихом п, она неприводима тогда и только тогда, когда м +1 простое и п примитивный корень по модулю м + 1)
• Единственный АОП, который примитивный многочлен является Икс² + х + 1.

Несмотря на то, что вес Хэмминга велик, из-за простоты представления и других улучшений существуют эффективные реализации в таких областях, как теория кодирования и криптография.^[1]

Над ${\displaystyle \mathbb {Q} }$АОП неприводимо, если м + 1 простое число p, поэтому в этих случаях пth циклотомический многочлен.^[4]

Рекомендации

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

внешняя ссылка

• все один многочлен в PlanetMath.