Примитивный многочлен над конечным полем

Примитивный многочлен над конечным полем задаёт элемент расширения, степени которого перебирают все ненулевые элементы этого расширения. В информатике это свойство используют при построении последовательностей максимального периода. Оно сильнее неприводимости: многочлен может быть неприводимым, но его корень вернётся к единице слишком рано. Посмотрите на два примера четвёртой степени в калькуляторе: выберите многочлен и меняйте показатель степени, чтобы увидеть остатки и длину цикла.
Что означает примитивность над конечным полем
Пусть - поле из элементов, а - унитарный неприводимый многочлен степени над этим полем. Унитарный означает, что коэффициент при старшей степени равен единице. Возьмём корень многочлена в расширении . Многочлен называют примитивным, если порождает всю мультипликативную группу ненулевых элементов поля:
Порядок - наименьшее положительное число , для которого . Указанное число максимально возможно, поскольку ненулевых элементов ровно . Все корни неприводимого многочлена над конечным полем имеют одинаковый порядок, поэтому выбор корня не меняет ответа. Подробные определения через минимальный многочлен и генератор группы приведены в работе о примитивных многочленах и регистрах.
На видео показано умножение на с последующим взятием остатка. Четыре бита обозначают коэффициенты при , , и слева направо. Например, 0011 означает , а не десятичное число одиннадцать. В конце движение идёт обратно, чтобы цикл просмотра был плавным; обратный ход не является следующим шагом вычисления.
Как связаны остатки и элементы поля
В качестве примера возьмём , где сложение коэффициентов выполняется по модулю двух: . Многочлен
неприводим над . Поэтому классы остатков по модулю образуют поле из элементов. Каждый остаток единственным образом записывается многочленом степени меньше четырёх. Если обозначить класс через , то из получим .
Теперь можно последовательно умножать на . Начало цепочки таково:
Здесь сокращение степени - это деление многочленов с остатком над . После 15 различных ненулевых остатков получается снова : порядок равен 15, и примитивен. В битовой записи первые переходы выглядят как 0001 → 0010 → 0100 → 1000 → 0011. На последнем переходе появившийся член заменяется на ; сложение коэффициентов выполняется операцией XOR. Это же правило применяется дальше на каждом шаге. Ноль в этот цикл не входит: произведение двух ненулевых элементов поля ненулевое. Остатки позволяют работать с расширением без поиска численных значений корней: выражение сокращают по заданному многочлену, а коэффициенты складывают по модулю двух. Две разные записи задают один и тот же элемент, если их разность делится на определяющий многочлен. Остаток степени меньше четырёх выбирает из каждого такого класса единственного представителя. Связь корня и определяющего его многочлена помогает понять статья о минимальном многочлене элемента поля.
Неприводимости недостаточно
Сравним с другим многочленом той же степени:
Он тоже неприводим над , но не примитивен. Действительно, в характеристике два
Следовательно, для класса выполняется . Сам не равен единице, а 5 - простое число, поэтому его порядок равен 5. Его степени дают лишь пять из пятнадцати ненулевых элементов. Другие ненулевые элементы поля существуют, но именно степени этого корня до них не доходят.

Оба результата можно проверить в инструменте: столбцы представляют остатки как числа от 1 до 15. Для уже на степени 5 повторяется остаток 0001. Для он впервые повторяется на степени 15. Числовая высота столбца - лишь удобная запись битов, а не порядок элемента.
Проверка порядка без полного перебора
После доказательства неприводимости степень расширения известна. Положим и разложим на простые множители. Для ненулевого достаточно проверить
Почему этого хватает? Порядок элемента делит . Если бы он был собственным делителем , то число имело бы простой делитель , а значит, . Обратное тоже верно: равенство единице на любой из этих степеней показывает, что порядок меньше . Степени удобно вычислять последовательным возведением в квадрат и после каждого умножения брать остаток по модулю . Для каждого простого делителя достаточно одной проверки, даже если он входит в разложение несколько раз. При вычислении важно не путать деление показателя на с делением многочлена: первое выполняют в целых числах, второе - над выбранным полем.
Для имеем . Достаточно проверить два остатка:
Следовательно, порядок равен 15. Важно не пропускать первый этап: без неприводимости факторкольцо может не быть полем, и приведённое объяснение через группу из элементов неприменимо.
Как проверить неприводимость в примере
Для многочлена четвёртой степени над достаточно исключить линейные и квадратичные множители. Если он приводим, в разложении обязательно найдётся множитель степени один или два. Линейные множители проверяют подстановкой и : у обоих выбранных многочленов корней в нет.
Единственный неприводимый унитарный квадратный многочлен над - . По модулю имеем и . Остатки от деления и на равны соответственно и , так что ни один из них на не делится. Это завершает проверку неприводимости обоих. Здесь перечисление возможно потому, что поле и степень малы. В частности, квадратный многочлен без корней обязан быть неприводимым: при разложении квадрата один из множителей имел бы степень один. Для больших степеней используют алгоритмы над конечными полями; критерий Эйзенштейна относится к другой постановке и не заменяет такую проверку.
Зачем это регистру сдвига
Линейный регистр сдвига с обратной связью обновляет конечное число битов по линейному правилу над . При согласованном выборе характеристического многочлена степени примитивность даёт период для каждого ненулевого начального состояния. Это максимальное число таких состояний; нулевое состояние остаётся нулевым. Связь характеристического многочлена и периода сформулирована в исследовании о примитивных регистрах.
При реализации нужно явно указать соглашение о порядке битов, направлении сдвига и том, записан ли характеристический или обратный к нему многочлен: одни и те же коэффициенты в разных соглашениях дают разные схемы соединений. При этом период относится к состоянию регистра, а не просто к числу возможных вариантов на выходном проводе. Для конкретной выходной последовательности важно также указать, какой бит считывается и как устроена схема. Максимальный период сам по себе не гарантирует криптографическую стойкость: линейное правило можно восстанавливать по наблюдениям. Такие последовательности полезны для учебных моделей, тестовых сигналов и кодирования, когда свойства конструкции проверены для конкретной задачи.
Другое значение: целые коэффициенты
В алгебре термин используется и иначе. Ненулевой многочлен из называют примитивным, если наибольший общий делитель его коэффициентов равен единице. Например,
Содержание исходного многочлена равно 3, а примитивная часть имеет содержание 1. При этом она раскладывается как : примитивность над целыми не означает неприводимость. Лемма Гаусса связывает содержание произведения с содержаниями множителей и позволяет переходить между разложениями над и для примитивного многочлена. Чтобы найти примитивную часть, берут неотрицательный НОД абсолютных значений всех коэффициентов, включая нулевые, и делят на него каждый коэффициент. Знак при этом остаётся в многочлене; нулевой многочлен рассматривают отдельно, поскольку делить все его коэффициенты на ноль нельзя. Слово «примитивный» встречается и в названии примитивно рекурсивных функций, но там оно обозначает класс функций и никак не проверяет многочлен. Оба значения термина для многочленов собраны в Encyclopedia of Mathematics. Для сравнения условий неприводимости над рациональными числами см. разбор критерия Эйзенштейна над Q.
Частые ошибки
- Считать неприводимость достаточной. Пример показывает порядок 5 вместо 15.
- Включать ноль в мультипликативный цикл. Степени ненулевого элемента лежат только среди ненулевых элементов поля.
- Проверять только . Это равенство выполняется для любого ненулевого элемента поля и не доказывает максимальность порядка.
- Смешивать два определения примитивности. НОД коэффициентов над целыми и порядок корня над конечным полем отвечают на разные вопросы.
FAQ
Любой ли многочлен с единичным старшим коэффициентом примитивен?
Нет. Унитарность фиксирует нормировку. Дополнительно нужны неприводимость и максимальный порядок корня в соответствующем конечном поле.
Можно ли получить период 16 у четырёхбитового линейного регистра?
Для линейного регистра с примитивным характеристическим многочленом ненулевой цикл имеет длину 15. Нулевое состояние образует отдельный цикл длины один.
Зависит ли ответ от поля коэффициентов?
Да. Неприводимость и порядок проверяют относительно конкретного поля. Прежде чем вычислять остатки, укажите поле и правила арифметики в нём.
Коротко
Над примитивный многочлен степени неприводим, а его корень имеет порядок . Проверка сочетает неприводимость с тестами степеней для простых делителей этого числа. Над целыми слово «примитивный» означает единичный НОД коэффициентов и описывает другое свойство.
Читайте также

Эллиптические кривые в криптографии: точки и ключи
Как эллиптические кривые применяют для обмена ключами и цифровых подписей: сложение точек над конечным полем, учебный расчёт, ECDH и границы стойкости ECC.

Неприводимый многочлен над полем: определение и примеры
Что такое неприводимый многочлен над полем, как проверить его для степеней два и три и почему ответ зависит от поля. Примеры над Q, R и конечными полями.

Схема разделения секрета Шамира: порог k из n
Схема разделения секрета Шамира простыми словами: как полином над конечным полем делит секрет на n долей с порогом k, как восстановить значение интерполяцией Лагранжа и где это применяют.

Абсолютно неупругий удар: сохранение импульса
Как найти скорость тел после абсолютно неупругого удара, применить закон сохранения импульса и вычислить потерю кинетической энергии на понятных примерах с формулами.

Абсолютное и избыточное давление: формулы и вакуум
Абсолютное и избыточное давление, разрежение и вакуум: как выбрать начало отсчёта, перевести показания манометра и решить задачи с примерами в килопаскалях.

АЦП последовательного приближения: схема и принцип работы
Разберите схему АЦП последовательного приближения: как компаратор, ЦАП и регистр определяют код по битам, как вычислить шаг квантования и оценить погрешность.