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

Primitive polynomial (field theory)

В теория поля, филиал математика, а примитивный многочлен это минимальный многочлен из примитивный элемент из конечный поле расширения GF(пм). Другими словами, полином F(Икс) с коэффициентами в GF (п) = Z/пZ является примитивным многочленом, если его степень м и у него есть корень α в ГФ (пм) такие, что {0, 1, α, α2, α3, ..., αпм−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 (пм) можно представить как последовательные степени α:

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

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

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

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

Например, учитывая примитивный многочлен p (x) = Икс10 + Икс3 + 1, мы начинаем с заданного пользователем ненулевого 10-битового начального числа, занимающего битовые позиции с 1 по 10, которые представляют коэффициенты полинома над GF (2), начиная с наименее значимого бита. (Семя необязательно выбирать случайным образом, но это возможно). Затем начальное число сдвигается влево на одну позицию, так что 0-й бит перемещается в позицию 1, которая выполняет умножение на x, примитивный элемент GF (2 ^ 10) [x] / p (x). Затем мы берем 10-й и 3-й бит и создаем новый 0-й бит, чтобы xor из трех битов равен 0, что обеспечивает деление по модулю p (x). Этот процесс можно повторить для создания 210 − 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] Это можно использовать для создания генератора псевдослучайных чисел огромного периода. 274207281 − 13×1022338617.

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

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

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