Введение

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

В теории конечных полей, являющейся разделом математики, примитивный полином – это минимальный полином примитивного элемента конечного поля GF(p^m). Это означает, что многочлен F(X) степени m с коэффициентами из GF(p) = Z/pZ является примитивным полиномом, если он является моноичным и имеет корень α в GF(p^m) таким образом, что {1, α, α², ..., α^(p^m-1)} составляет всё поле GF(p^m). Это подразумевает, что α является примитивным корнем степени (p^m − 1) из единицы в GF(p^m).

Свойства

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

Примеры

По GF(3) многочлен x^(2) + 1 является неприводимым, но не примитивным, поскольку он делит x^(4) − 1: его корни генерируют циклическую группу порядка 4, в то время как мультипликативная группа GF(3^(2)) является циклической группой порядка 8. Многочлен x^(2) + 2x + 2, с другой стороны, является примитивным. Обозначим один из его корней через α. Тогда, поскольку натуральные числа, меньшие и взаимно простые с 8, это 1, 3, 5 и 7, четыре примитивных корня в GF(3^(2)) равны α, α^(3), α^(5) и α^(7). Примитивные корни α и α^(3) алгебраически сопряжены. Действительно, остальные примитивные корни α^(5) и α^(7) также алгебраически сопряжены и порождают второй примитивный многочлен. Для степени 3, GF(3^(3)) имеет 26 примитивных элементов. Поскольку каждый примитивный многочлен 3-й степени имеет три корня, все они обязательно примитивны, существует 26/3 = 8 (округлённо) примитивных многочлена 3-й степени. Один примитивный многочлен — это x^(3) + 2x + 1. Обозначив один из его корней через γ, алгебраически сопряжёнными элементами являются γ^(3) и γ^(9). Другие примитивные многочлены связаны с алгебраически сопряжёнными множествами, построенными на других примитивных элементах γ^(r) с r, взаимно простым с 26.

Псевдослучайная генерация битов

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

Коды CRC

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

Первобытные триномии

Полезным классом примитивных многочленов являются примитивные триномы, содержащие только три ненулевых члена: x^r + x^k + 1. Их простота обеспечивает создание особенно компактных и быстрых линейных регистров сдвига с обратной связью. Существует ряд результатов, предлагающих методы поиска и проверки примитивности триномов. Для многочленов над GF(2), где 2^r − 1 является простым числом Мерсенна, многочлен степени r является примитивным тогда и только тогда, когда он неприводим. (При заданном неприводимом многочлене, он не будет примитивным только в том случае, если период x является нетривиальным делителем 2^r − 1. Простые числа не имеют нетривиальных делителей.) Хотя генератор псевдослучайных чисел Mersenne Twister не использует трином, он использует этот факт. Ричард Брент составляет таблицы примитивных триномов этой формы, например, x^74207281 + x^30684570 + 1. Это можно использовать для создания генератора псевдослучайных чисел с огромным периодом 2^74207281 − 1 ≈ 3.