Войти
В теории поля, ветвь математики, примитивный многочлен - это минимальный многочлен примитивного элемента конечного поле расширения GF (p). Другими словами, многочлен F (X) с коэффициентами в GF (p) = Z/pZявляется примитивным многочленом, если его степень равна m и у него есть корень α в GF (p) такой, что {0, 1, α, α, α,..., α} - все поле 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.
Над GF (p) имеется ровно φ (p - 1) / m примитивных многочленов степени m, где φ - функция Эйлера.
Примитивный многочлен степени m имеет m различных корней в GF (p), все из которых имеют порядок p - 1. Это означает, что если α - такой корень, то α = 1 и α ≠ 1 для 0 < i < p − 1.
Примитивный многочлен F (x) степени m примитивного элемента α в GF (p) имеет явный вид F (x) = (x - α) (x - α) (x - α) ⋅⋅⋅ (х - α).
Примитивные полиномы используются в представлении элементов конечного поля. Если α в GF (p) является корнем примитивного многочлена F (x), то, поскольку порядок α равен p - 1, это означает, что все ненулевые элементы GF (p) могут быть представлены как последовательные степени α:
Когда эти элементы сокращаются по модулю F (x), они обеспечивают полиномиальное представление всех элементов поля.
Поскольку мультипликативная группа конечного поля всегда является циклической группой, примитивный многочлен f - это многочлен, такой что x является генератором мультипликативной группы в GF (p) [x] / f (x)
Примитивные полиномы над GF (2), полем с двумя элементами, могут использоваться для генерация псевдослучайных битов. Фактически, каждый регистр сдвига с линейной обратной связью с максимальной длиной цикла (которая составляет 2 - 1, где n - длина сдвигового регистра с линейной обратной связью) может быть построен из примитивного полинома.
Например, учитывая примитивный полином x + x + 1, мы начинаем с заданного пользователем ненулевого 10-битного начального числа, занимающего позиции битов с 1 по 10, начиная с младшего значащего бита. (Семя необязательно выбирать случайным образом, но это возможно). Затем мы берем 10-й и 3-й биты и создаем новый 0-й бит, так что xor из трех битов равен 0. Затем начальное число сдвигается влево на одну позицию, так что 0-й бит перемещается в позицию 1. Этот процесс можно повторить для генерации 2 - 1 = 1023 псевдослучайных битов.
В общем, для примитивного полинома степени m над GF (2) этот процесс будет генерировать 2–1 псевдослучайный бит перед повторением той же последовательности.
Проверка циклическим избыточным кодом (CRC) - это код обнаружения ошибок, который работает, интерпретируя строку битов сообщения как коэффициенты полинома над GF (2) и делением на фиксированный образующий многочлен также над GF (2); см. Математика CRC. Примитивные полиномы или их кратные числа иногда являются хорошим выбором для порождающих полиномов, поскольку они могут надежно обнаруживать две битовые ошибки, которые возникают далеко друг от друга в битовой строке сообщения, на расстоянии 2 - 1 для примитивного полинома степени n.
Полезным классом примитивных многочленов являются примитивные трехчлены, имеющие только три ненулевых члена: x + x + 1. Их простота делает особенно маленькими и быстрыми линейными регистры сдвига обратной связи. Ряд результатов дает методы для обнаружения и проверки примитивности трехчленов.
Для многочленов над GF (2), где 2-1 является простым числом Мерсенна, многочлен степени r примитивен тогда и только тогда, когда он неприводим. (Учитывая неприводимый многочлен, он не примитивен, только если период x является нетривиальным множителем 2-1. Простые числа не имеют нетривиальных множителей.) Хотя Mersenne Twister псевдослучайное число генератор не использует трехчлен, он использует это преимущество.
Ричард Брент составлял таблицы примитивных трехчленов этой формы, например x + x + 1. Это можно использовать для создания генератора псевдослучайных чисел с огромным периодом 2 - 1 ≈ 3 × 10.
