Примитивный полином (теория поля)

В теории конечного поля , разделе математики , примитивный многочлен — это минимальный многочлен конечного примитивного элемента GF поля $(p м)$ . Это означает, что многочлен $F (X)$ степени $m$ с коэффициентами из $GF(p) = Z / p Z$ является примитивным многочленом , если он унитарный и имеет корень $α$ в $GF(p м)$ такой, что $\{0,1,\alpha ,\alpha ^{2},\alpha ^{3},\ldots \alpha ^{p^{m}-2}\}$ – все поле $GF(p м)$ . Отсюда следует, что $α$ является примитивом ( $p м - 1$ )-корень из единицы в $GF(p м)$ .

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

Поскольку все минимальные многочлены неприводимы , все примитивные многочлены также неприводимы.
Примитивный многочлен должен иметь ненулевой постоянный член, иначе он будет делиться на x . В GF(2) x + 1 является примитивным многочленом, а все остальные примитивные многочлены имеют нечетное количество членов, поскольку любой многочлен по модулю 2 с четным количеством членов делится на x + 1 (он имеет 1 в качестве корня) .
F Неприводимый многочлен ( x ) степени m над GF( p ), где p — простое число, является примитивным многочленом, если наименьшее положительное целое число n такое, что F ( x ) делит x ^н − 1 — это n = p ^м − 1 .
Примитивный полином степени $m$ имеет $m$ различных корней в $GF(p м)$ , которые все имеют порядок $p м - 1$ , что означает, что любой из них порождает мультипликативную группу поля.
Над GF( p ) существует ровно $φ (p м - 1)$ примитивные элементы и $φ (p м - 1) / m$ примитивных многочленов, каждый степени $m$ , где $φ$ — функция Эйлера . ^[1]
Алгебраические сопряжения примитивного элемента $α$ из $GF(p м)$ представляют $собой$ , $а п$ , $а п 2$ , ..., $а п м -1$ и поэтому примитивный полином $F (x)$ имеет явный вид $F (x) = (x - α) (x - α п) (х - а п 2) \dots (х - а п м -1)$ . Что коэффициенты полинома такого вида для любого $α$ из $GF(p н)$ , не обязательно примитивные, лежат в $GF(p)$ следует из того свойства, что многочлен инвариантен относительно применения автоморфизма Фробениуса к его коэффициентам (с использованием $α п н = α$ ) и из того факта, что фиксированным полем автоморфизма Фробениуса является $GF(p)$ .

Примеры

Над $GF(3)$ полином $x 2 + 1$ неприводимо, но не примитивно, поскольку делит $x 4 - 1$ : его корни порождают циклическую группу порядка 4, а мультипликативная группа $GF(3 2)$ — циклическая группа порядка 8. Многочлен $x 2 + 2 x + 2$ , с другой стороны, примитивно. Обозначим один из его корней через $α$ . Тогда, поскольку натуральные числа меньше 3 и относительно просты с $32 - 1 = 8$ — это 1, 3, 5 и 7 — четыре примитивных корня в $GF(3 2)$ представляют $собой$ , $а 3 = 2 а + 1$ , $а 5 = 2 а$ и $а 7 = а + 2$ . Примитивные корни $α$ и $α 3$ алгебраически сопряжены. действительно $х 2 + 2 Икс + 2 знак равно (Икс - α) (Икс - (2 α + 1))$ . Остальные примитивные корни $α 5$ и $α 7 = (а 5) 3$ также алгебраически сопряжены и дают второй примитивный полином: $x 2 + Икс + 2 знак равно (Икс - 2 α) (Икс - (α + 2))$ .

Для степени 3 $GF(3 3)$ имеет $φ (3 3 - 1) = φ (26) = 12$ примитивных элементов. Поскольку каждый примитивный многочлен степени 3 имеет три корня, обязательно примитивных, существует $12/3 = 4$ примитивных многочлена степени 3. Один примитивный многочлен - это $x 3 + 2 х + 1$ . Обозначая один из его корней через $γ$ , алгебраически сопряженными элементами являются $γ 3$ и $γ 9$ . Остальные примитивные многочлены связаны с алгебраически сопряженными множествами, построенными на других примитивных элементах $γ. р$ где $r$ относительно простое число 26:

{\begin{aligned}x^{3}+2x+1&=(x-\gamma )(x-\gamma ^{3})(x-\gamma ^{9})\\x^{3}+2x^{2}+x+1&=(x-\gamma ^{5})(x-\gamma ^{5\cdot 3})(x-\gamma ^{5\cdot 9})=(x-\gamma ^{5})(x-\gamma ^{15})(x-\gamma ^{19})\\x^{3}+x^{2}+2x+1&=(x-\gamma ^{7})(x-\gamma ^{7\cdot 3})(x-\gamma ^{7\cdot 9})=(x-\gamma ^{7})(x-\gamma ^{21})(x-\gamma ^{11})\\x^{3}+2x^{2}+1&=(x-\gamma ^{17})(x-\gamma ^{17\cdot 3})(x-\gamma ^{17\cdot 9})=(x-\gamma ^{17})(x-\gamma ^{25})(x-\gamma ^{23}).\end{aligned}}

Приложения

Представление элемента поля

Примитивные полиномы можно использовать для представления элементов конечного поля . Если α в GF( p ^м) является корнем примитивного многочлена F ( x ), то ненулевые элементы GF( p ^м) представлены как последовательные степени α :

\mathrm {GF} (p^{m})=\{0,1=\alpha ^{0},\alpha ,\alpha ^{2},\ldots ,\alpha ^{p^{m}-2}\}.

Это позволяет экономично представить в компьютере ненулевые элементы конечного поля, представляя элемент соответствующим показателем степени. $\alpha .$ Это представление упрощает умножение, поскольку оно соответствует сложению показателей степени по модулю. $p^{m}-1.$

Генерация псевдослучайных битов

Примитивные полиномы над GF(2), полем с двумя элементами, можно использовать для генерации псевдослучайных битов . Фактически, каждый сдвиговый регистр с линейной обратной связью с максимальной длиной цикла (которая составляет 2 ^н − 1 , где n — длина регистра сдвига с линейной обратной связью) может быть построена из примитивного полинома. ^[2]

В общем, для примитивного полинома степени m над GF(2) этот процесс будет генерировать 2 ^м − 1 псевдослучайный бит перед повторением той же последовательности.

CRC-коды

Проверка циклическим избыточным кодом (CRC) — это код обнаружения ошибок, который интерпретирует битовую строку сообщения как коэффициенты полинома по GF(2) и делит ее на фиксированный генераторный полином также по GF(2); см. Математика CRC . Примитивные полиномы или кратные им полиномы иногда являются хорошим выбором для генераторных полиномов, поскольку они могут надежно обнаруживать две битовые ошибки, которые происходят далеко друг от друга в битовой строке сообщения, на расстоянии до 2. ^н − 1 для примитивного полинома степени n .

Примитивные трехчлены

Полезным классом примитивных многочленов являются примитивные трехчлены, имеющие только три ненулевых члена: x ^р + х ^к + 1 . Их простота делает регистры сдвига с линейной обратной связью особенно маленькими и быстрыми . ^[3] Ряд результатов дает методы обнаружения и проверки примитивности трехчленов. ^[4]

Для полиномов над GF(2), где 2 ^р − 1 — простое число Мерсенна , многочлен степени r примитивен тогда и только тогда, когда он неприводим. (Данный неприводимый полином не является примитивным только в том случае, если период x является нетривиальным множителем 2 ^р − 1 . Простые числа не имеют нетривиальных множителей.) Хотя Mersenne Twister генератор псевдослучайных чисел не использует трехчлен, он все же пользуется этим.

Ричард Брент составлял таблицы примитивных трехчленов этой формы, таких как x ^74207281 + х ^30684570 + 1 . ^[5]^[6] Это можно использовать для создания генератора псевдослучайных чисел огромного периода 2. ^74207281 − 1 ≈ 3 × 10 ^{22 338 617}.

Ссылки

^ Перечисления примитивных полиномов по степени над $GF(2)$ , $GF(3)$ , $GF(5)$ , $GF(7)$ и $GF(11)$ даны последовательностями A011260 , A027385 , A027741 , A027743 и A319166 в Интернете. Энциклопедия целочисленных последовательностей .
^ К. Паар, Дж. Пельцль - Понимание криптографии: учебник для студентов и практиков
^ Нежный, Джеймс Э. (2003). Генерация случайных чисел и методы Монте-Карло (2-е изд.). Нью-Йорк: Спрингер. п. 39. ИСБН 0-387-00178-6 . OCLC 51534945 .
^ Зирлер, Нил; Бриллхарт, Джон (декабрь 1968 г.). «О примитивных трехчленах (Мод 2)». Информация и контроль . 13 (6): 541, 548, 553. doi : 10.1016/S0019-9958(68)90973-X .
^ Брент, Ричард П. (4 апреля 2016 г.). «Поиск примитивных трехчленов (мод 2)» . Проверено 25 мая 2024 г.
^ Брент, Ричард П .; Циммерманн, Пол (24 мая 2016 г.). «Двенадцать новых примитивных бинарных трёхчленов». arXiv : 1605.09213 [ math.NT ].

Внешние ссылки

Вайсштейн, Эрик В. «Примитивный полином» . Математический мир .

[1] Перечисления примитивных полиномов по степени над $GF(2)$ , $GF(3)$ , $GF(5)$ , $GF(7)$ и $GF(11)$ даны последовательностями A011260 , A027385 , A027741 , A027743 и A319166 в Интернете. Энциклопедия целочисленных последовательностей .

[2] К. Паар, Дж. Пельцль - Понимание криптографии: учебник для студентов и практиков

[3] Нежный, Джеймс Э. (2003). Генерация случайных чисел и методы Монте-Карло (2-е изд.). Нью-Йорк: Спрингер. п. 39. ИСБН 0-387-00178-6 . OCLC 51534945 .

[4] Зирлер, Нил; Бриллхарт, Джон (декабрь 1968 г.). «О примитивных трехчленах (Мод 2)». Информация и контроль . 13 (6): 541, 548, 553. doi : 10.1016/S0019-9958(68)90973-X .

[5] Брент, Ричард П. (4 апреля 2016 г.). «Поиск примитивных трехчленов (мод 2)» . Проверено 25 мая 2024 г.

[6] Брент, Ричард П .; Циммерманн, Пол (24 мая 2016 г.). «Двенадцать новых примитивных бинарных трёхчленов». arXiv : 1605.09213 [ math.NT ].

[1]

[2]

[3]

[4]

[5]

[6]