Примитивный многочлен (алгебра)
В алгебре примитивный многочлен — это всякий многочлен ![f(x)\in R[x]](https://dic.academic.ru/dic.nsf/ruwiki/c73681c532005617794246d16a13e6d1.png)
, где 
— ассоциативно-коммутативное кольцо с однозначным разложением на множители, коэффициенты которого не имеют нетривиальных общих делителей.
Любой многочлен ![g(x)\in R[x]](https://dic.academic.ru/dic.nsf/ruwiki/f2805a920dccd7d29fa8809c662fca09.png)
можно записать в виде 
, где 
— примитивный многочлен, a 
— наибольший общий делитель коэффициентов многочлена 
. Элемент 
, определён с точностью до умножения на обратимые элементы из R, он называется содержанием многочлена .
Свойства
- Лемма Гаусса: если
![g_1(x),g_2(x)\in R[x]](https://dic.academic.ru/dic.nsf/ruwiki/e1fdc5e4e7d5883b5942d7dfd0b88d8a.png)
, то 
Теперь мы можем выполнять умножение в поле расширения, не зная даже таблицы умножения этого поля. Например: а 5 -а 6 = а 11 = а 4 -а 7 = а 4 -1 = а 4 = а 2 + а. Сложение в таком поле выполняется еще проще. Для этого достаточно сложить соответствующие степени примитивного элемента а по законам сложения исходного поля GF(2), то есть по модулю 2: а 5 + а 6 = (а 2 + а + 1) + (а 2 + 1) = а. В обоих случаях не требуется вычислять остаток от деления, а также выполнять поэлементное умножение соответствующих степеней, как в случае умножения в кольце многочленов.
Поскольку любой ненулевой элемент поля в этом случае соответствует некоторой степени элемента а, то для деления элементов в таком поле нет необходимости искать обратные мультипликативные элементы. Достаточно выполнить вычитание степеней, как при арифметическом делении разных степеней одного и того же числа. Например, в поле GF(2 3 ) а 2 -а 3 = а 5 = а 2 + а + 1. Кроме того, так как а^ -1 -1 = 1, то при получении отрицательной степени в результате деления также достаточно просто найти соответствующий элемент положительной степени. Например, в поле GF(2 3 ) а 5 /а 8 = а -3 . Так как в этом случае q m —1 = 7 и а 7 = = 1, то а -3 = 1/а 3 = а 7 /а 3 = а 4 .
Несмотря на то, что процесс деления не требует поиска обратного мультипликативного элемента, такой элемент все же существует для любого элемента и может быть легко найден из равенства а^» 7 — 1 — 1 = 1. Например, обратным мультипликативным элементом элемента а 7 будет элемент а 8 , так как а 15 = 1
и (а 7 ) -1 = 1/а 7 = а 15 /а 7 = а 8 .
Обратный аддитивный элемент любого элемента поля в этом случае всегда равен исходному элементу поля.
Таким образом, мы определили объект, обладающий всеми свойствами поля. При этом полученное поле характеризуется исключительно простыми операциями сложения и умножения.
В примере 1.4.3 построения поля GF(2 3 ) примитивным элементом оказался корень выбранного неприводимого многочлена. Однако это выполняется далеко не для всех неприводимых многочленов над полем GF(2).
Рассмотрим, например, многочлен р(х) = х 4 + х 3 + х 2 + х+’ над GF( 2). Проверив все возможные делители, можно убедиться в том, что этот многочлен делится только сам на себя и на 1 и, следовательно, неприводим в GF(2). Однако, определяя ненулевые элементы поля GF(2 3 ) как степени корня (3 рассматриваемого многочлена, можно получить лишь пять неповторяющихся элементов:
Проверив все возможные комбинации, можно определить, что примитивным в данном случае является элемент (3 + 1:
то элемент (3 + 1 не является корнем многочлена х* + х* + х 2 + х+’.
Таким образом, можно сделать вывод о том, что поле может быть построено из кольца многочленов по модулю любого неприводимого многочлена. И это поле будет соответствовать рассмотренному в параграфе 1.2 полю многочленов.
Однако при построении поля расширения по степеням примитивного элемента, равного корню неприводимого в простом поле многочлена, требуется дополнительный критерий выбора неприводимого многочлена. Дело в том, что среди неприводимых многочленов существует особый класс многочленов, называемых примитивными многочленами.
Например, в случае многочлена х 3 + х + 1 степени переменной х по модулю указанного многочлена образуют все ненулевые элементы GF(2 3 ) как поля многочленов:
В таком поле примитивный элемент всегда известен заранее.
Следует отметить, что примитивный многочлен должен отвечать еще одному условию. Ниже, в параграфе 1.5, будет показано, что корнями примитивного многочлена степени т над полем GF(q), помимо примитивного элемента поля расширения GF(q m ), являются также т — 1 других элементов поля GF
Поэтому разложение примитивного многочлена можно записать следующим образом:
где (3i = а — примитивный элемент поля расширения GF(q m ). Ясно, что элемент а и остальные элементы поля GF(q m ) в разложении многочлена р <х)также будут корнями многочлена а-р(х), где а Ф 0 — произвольный элемент (константа) поля GF(q).
Таким образом, коэффициент at 1 не меняет представление элементов поля расширения, построенного по степеням корня а-р(х), однако усложняет процедуру построения поля. Поэтому к примитивному многочлену предъявляют еще одно условие: коэффициент при старшей степени неопределенной переменной примитивного многочлена должен быть равен единице.
Многочлен, старший коэффициент которого равен единице, называется нормированным многочленом.
Таким образом, примитивный многочленр(х) =x m + pm-rx m_1 + рт-гх т
2 + + . + ргх + ро степени т > 1 — это нормированный неприводимый над полем GF(q) многочлен, корень которого соответствует примитивному элементу расширения GF(q m ) поля GF(q), построенного по модулю р(х).
В предыдущих двух параграфах мы определили способы построения и условия существования полей целых чисел и полей многочленов над полями целых чисел. При этом мы определяли поле многочленов не как поле расширения простого поля, а как некое самостоятельное поле. Теперь же мы можем достаточно просто определить поле как расширение GF(q m ) исходного поля GF(q).
В поле расширения по модулю неприводимого и не примитивного многочлена необходимо определять все элементы и строить таблицы сложения и умножения или каждый раз при необходимости сложить или умножить элементы поля производить довольно непростые вычисления. Кроме того, в случае отсутствия таблицы умножения деление в таком поле связано с поиском обратного мультипликативного элемента при помощи алгоритма Евклида. Даже в полях расширения небольших порядков все это представляет большую сложность.
Полученное в этом параграфе представление поля расширения GF(q m ) является наиболее удобным, и далее мы будем работать именно с таким представлением поля расширения. Поэтому условимся, что далее под полем расширения GF(q m ) будем иметь в виду именно поле, построенное по модулю примитивного многочлена.
Следует все же отметить, что и у этого представления поля есть свои недостатки. А именно — представление степени примитивного элемента в виде суммы степеней, например, для выполнения сложения. К примеру, в поле GF(2 8 ), с которым мы еще не раз встретимся ниже, уже достаточно трудно выполнять сложение. В качестве примера читателю предлагается выполнить сложение элементов а 131 и а 218 и представить результат в виде степени примитивного элемента поля расширения GF(2 8 ). Примитивный многочлен степени 8 над GF(2) в этом случае р<х) = х 8 + х А + х 3 + х 2 + '.
Примитивный многочлен, его свойства
Доказательство. Из определения разности порядка k выразим разность меньшего порядка . Продолжив этот процесс получим искомую формулу.
Определение 2.2Многочлен над кольцом целых чисел называется примитивным, если наибольший общий делитель его коэффициентов равен 1.
Многочлен с рациональными коэффициентами единственным образом представляется в виде произведения положительного рационального числа и примитивного многочлена. Рациональное число называют содержанием многочлена.
Теорема 2.10 Произведение примитивных многочленов есть примитивный многочлен.
Доказательство проведём методом от противного. Пусть произведение двух примитивных многочленов и есть не примитивный многочлен . Найдётся простое число p, которое делит все коэффициенты многочлена h(x) без остатка. Пусть -самый младший (с наименьшим номером) коэффициент f(x), не делящийся на p без остатка (такой найдётся в силу примитивности многочлена), а — самый младший коэффициент g(x), не делящийся на p без остатка. Коэффициент многочлена h(x) при вычисляется по формуле . Слагаемое делится на p без остатка при s<i, так как левый множитель кратен p, а при s>i, так как правый множитель кратен p. Единственное слагаемое, которое не делится на p, получается при s=i. Следовательно, вся сумма не делится на p, а значит не все коэффициенты h(x) делятся на p, что противоречит сделанному допущению. Тем самым теорема доказана.
Следствие 2.2. Если многочлен с целочисленными коэффициентами приводим над полем рациональных чисел, то он приводим над кольцом целых чисел.
Доказательство. Разложим многочлен над полем рациональных чисел. Каждый множитель представим в виде произведения его содержания и примитивного многочлена. Произведение примитивных многочленов суть примитивный многочлен, поэтому произведение содержаний множителей равно содержанию исходного многочлена. Для завершения доказательства осталось заметить, что содержание исходного многочлена есть целое число.
Таким образом, задача разложения многочлена на неприводимые множители над полем рациональных чисел сводится к аналогичной задаче над кольцом целых чисел.
Примитивный полином (теория поля) — 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). Этот процесс можно повторить для создания 2 10 − 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 22 338 617 .