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

Минимальный многочлен примитивного элемента в конечном поле

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

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

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

Примеры

Над GF(3) многочлен x ² + 1 неприводим, но не примитивен, поскольку делит x ⁴ − 1 : его корни порождают циклическую группу порядка 4, в то время как мультипликативная группа GF(3 ² ) является циклической группой порядка 8. Многочлен x ² + 2 x + 2 , с другой стороны, примитивен. Обозначим один из его корней через α . Тогда, поскольку натуральные числа, меньшие и взаимно простые с 3 ² − 1 = 8, равны 1, 3, 5 и 7, четыре примитивных корня в GF(3 ² ) равны α , α ³ = 2 α + 1 , α ⁵ = 2 α и α ⁷ = α + 2 . Первообразные корни α и α ³ алгебраически сопряжены. Действительно, x ² + 2 x + 2 = ( x − α ) ( x − (2 α + 1)) . Оставшиеся примитивные корни α ⁵ и α ⁷ = ( α ⁵ ) ³ также алгебраически сопряжены и дают второй примитивный многочлен: x ² + x + 2 = ( x − 2 α ) ( x − ( α + 2)) .

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

${\displaystyle {\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 ^m ) является корнем примитивного многочлена F ( x ), то ненулевые элементы GF( p ^m ) представляются как последовательные степени α :

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

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

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

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

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

CRC-коды

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

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

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

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

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

Ссылки

1. Перечисления примитивных многочленов по степеням над GF(2) , GF(3) , GF(5) , GF(7) и GF(11) задаются последовательностями A011260, A027385, A027741, A027743 и A319166 в Онлайн-энциклопедии целочисленных последовательностей .
2. C. Paar, J. Pelzl - Понимание криптографии: Учебник для студентов и практиков
3. Джентл, Джеймс Э. (2003). Генерация случайных чисел и методы Монте-Карло (2-е изд.). Нью-Йорк: Springer. С. 39. ISBN 0-387-00178-6. OCLC  51534945.
4. Zierler, Neal; Brillhart, John (декабрь 1968). "On primitive trinomials (Mod 2)". Information and Control . 13 (6): 541, 548, 553. doi :10.1016/S0019-9958(68)90973-X.
5. Брент, Ричард П. (4 апреля 2016 г.). "Поиск примитивных трехчленов (mod 2)" . Получено 25 мая 2024 г.
6. Брент, Ричард П.; Циммерман , Пол (24 мая 2016 г.). «Двенадцать новых примитивных двоичных трехчленов». arXiv : 1605.09213 [math.NT].

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

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