Примитивный полином (теория поля) - Primitive polynomial (field theory)

Для многочленов, у которых наибольший общий делитель коэффициентов равен 1, см. Примитивный полином (теория колец).

В теория поля, филиал математика, а примитивный многочлен это минимальный многочлен из примитивный элемент из конечный поле расширения GF (п^м). Другими словами, полином F(Икс) с коэффициентами в GF (п) = Z/пZ является примитивным многочленом, если его степень м и у него есть корень α в ГФ (п^м) такие, что {0, 1, α, α², α³, ..., α^пм−2} - все поле GF (п^м). Это также означает, что α это примитивный (п^м − 1) -корень единства в ГФ (п^м).

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

Поскольку все минимальные многочлены равны несводимый, все примитивные многочлены также неприводимы.

Примитивный многочлен должен иметь ненулевой постоянный член, иначе он будет делиться наИкс. Над GF (2), Икс + 1 является примитивным многочленом, а все другие примитивные многочлены имеют нечетное число членов, так как любой многочлен по модулю 2 с четным числом членов делится на Икс + 1 (он имеет 1 в качестве корня).

An неприводимый многочлен F(Икс) степени м над GF (п), где п является простым, является примитивным многочленом, если наименьшее натуральное число п такой, что F(Икс) делит Икс^п − 1 является п = п^м − 1.

Более GF (п^м) есть ровно φ(п^м − 1)/м примитивные многочлены степени м, где φ является Функция Эйлера.

Примитивный многочлен степени м имеет м разные корни в GF (п^м), которые все имеют порядок п^м − 1. Это означает, что если α такой корень, то α^пм−1 = 1 и α^я ≠ 1 за 0 < я < п^м − 1.

Примитивный многочлен F(Икс) степени м примитивного элемента α в ГФ (п^м) имеет явный вид F(Икс) = (Икс − α)(Икс − α^п)(Икс − α^п2)⋅⋅⋅(Икс − α^пм−1).

Применение

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

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

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

Когда эти элементы сокращаются по модулю F(Икс) они обеспечивают полиномиальный базис представление всех элементов поля.

Поскольку мультипликативная группа конечного поля всегда циклическая группа, примитивный многочлен ж - многочлен такой, что Икс является генератором мультипликативной группы в GF (п)[Икс]/ж(Икс)

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

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

Например, учитывая примитивный многочлен p (x) = Икс¹⁰ + Икс³ + 1, мы начинаем с заданного пользователем ненулевого 10-битового начального числа, занимающего битовые позиции с 1 по 10, которые представляют коэффициенты полинома над GF (2), начиная с наименее значимого бита. (Семя необязательно выбирать случайным образом, но это возможно). Затем начальное число сдвигается влево на одну позицию, так что 0-й бит перемещается в позицию 1, которая выполняет умножение на x, примитивный элемент GF (2 ^ 10) [x] / p (x). Затем мы берем 10-й и 3-й бит и создаем новый 0-й бит, чтобы xor из трех битов равен 0, что обеспечивает деление по модулю p (x). Этот процесс можно повторить для создания 2¹⁰ − 1 = 1023 псевдослучайные биты.

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

Коды CRC

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

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

Полезный класс примитивных многочленов - это примитивные трехчлены, у которых есть только три ненулевых члена: Икс^р + Икс^k + 1. Их простота делает их очень маленькими и быстрыми. регистры сдвига с линейной обратной связью. Ряд результатов дает методы для обнаружения и проверки примитивности трехчленов.

Для полиномов над GF (2), где 2^р − 1 это Мерсенн прайм, многочлен степени р примитивен тогда и только тогда, когда он неприводим. (Для неприводимого полинома это нет примитивно только если период Икс является нетривиальным фактором 2^р − 1. У простых чисел нет нетривиальных множителей.) Хотя Мерсенн Твистер Генератор псевдослучайных чисел не использует трехчлен, он использует это в своих интересах.

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

использованная литература

1. К. Паар, Дж. Пельцль - Понимание криптографии: Учебник для студентов и практиков
2. Брент, Ричард П. (4 апреля 2016 г.). "Поиск примитивных триномов (мод. 2)". Получено 4 июн 2020.
3. Брент, Ричард П.; Циммерманн, Пауль (24 мая 2016 г.). «Двенадцать новых примитивных двоичных трехчленов» (PDF). arXiv:1605.09213 [math.NT ].

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

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