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