Полином Конвея (конечные поля)
В математике полином Конвея C p , n для конечного поля F p н — это особый неприводимый многочлен степени n над F p , который можно использовать для определения стандартного представления F p н как расщепления поле C p , n . Полиномы Конвея были названы в честь Джона Х. Конвея Ричардом А. Паркером , который первым дал им определение и вычислил примеры. Полиномы Конвея удовлетворяют определенному условию совместимости, предложенному Конвеем между представлением поля и представлениями его подполей. Они важны в компьютерной алгебре , где обеспечивают переносимость между различными математическими базами данных и системами компьютерной алгебры. Поскольку вычисление полиномов Конвея требует больших затрат, их необходимо сохранить, чтобы использовать на практике. Базы данных полиномов Конвея доступны в системах компьютерной алгебры GAP , [1] Маколей2 , [2] Магма , [3] МудрецМатематика , [4] на сайте Франка Любека, [5] и в Интернет-энциклопедии целочисленных последовательностей . [6]
Фон
[ редактировать ]Элементы F p н могут быть представлены в виде сумм вида a n −1 β п -1 + … + a 1 β + a 0 где β — корень неприводимого многочлена степени n над F p , а a j — элементы F p . Добавление элементов поля в этом представлении представляет собой просто сложение векторов. Хотя существует единственное конечное поле порядка p н с точностью до изоморфизма представление элементов поля зависит от выбора неприводимого многочлена. Полином Конвея — это способ стандартизировать этот выбор.
Ненулевые элементы конечного поля F образуют циклическую группу при умножении, обозначаемую F * . элемент Примитивный α из F p н — элемент, порождающий F * п н . Представление ненулевых элементов поля в виде степеней α позволяет эффективно выполнять умножение в поле. Примитивный полином для α — это монический многочлен наименьшей возможной степени с коэффициентами из F p, который имеет α как корень в F p. н ( минимальный полином для α ). Оно обязательно нередуцируемо. Полином Конвея выбран примитивным, так что каждый из его корней порождает мультипликативную группу соответствующего конечного поля.
Поле F p н содержит единственное подполе, изоморфное F p м для каждого m, делящего n , и это учитывает все подполя F p н . Для любого m, делящего n, циклическая группа F * п н содержит подгруппу, изоморфную F * п м . Если α порождает F * п н , то наименьшая степень α , порождающая эту подгруппу, равна α р где r = ( p н − 1) / ( п м − 1) . Если f n — примитивный полином для F p н с корнем α и f m является примитивным полиномом для F p м тогда по определению Конвея f m и f n совместимы , если α р корнем fm . является Это требует, чтобы f n ( x ) делило f m ( x р ) . называют это понятие совместимости нормосовместимостью Некоторые авторы . Полином Конвея для конечного поля выбирается таким образом, чтобы быть совместимым с полиномами Конвея каждого из его подполей. То, что сделать выбор таким образом можно, доказал Вернер Никель. [7]
Определение
[ редактировать ]Полином Конвея C p , n определяется как лексикографически минимальный монический примитивный многочлен степени n над F p , который совместим с C p , m для всех m, делящих n . Это индуктивное определение n : базовый случай — C p ,1 ( x ) = x − α , где α — лексикографически минимальный примитивный элемент F p . Используемое понятие лексикографического упорядочения заключается в следующем:
- Элементы F p упорядочены 0 < 1 < 2 < … < p − 1 .
- Многочлен степени d из F p [ x ] записывается a d x д − а d −1 x д -1 + … + (−1) д a 0 (с поочередным добавлением и вычитанием членов), а затем выражается в виде слова a d a d −1 … a 0 . Два многочлена степени d упорядочены в соответствии с лексикографическим порядком соответствующих им слов.
Поскольку, по-видимому, не существует какого-либо естественного математического критерия, который позволил бы выделить один монический примитивный полином, удовлетворяющий условиям совместимости, среди всех остальных, наложение лексикографического порядка в определении полинома Конвея следует рассматривать как соглашение.
Стол
[ редактировать ]Полиномы Конвея C p , n для наименьших значений p и n сведены в таблицу ниже. Все они были впервые вычислены Ричардом Паркером и взяты из таблиц Фрэнка Любека. Расчеты можно проверить, используя основные методы следующего раздела, с помощью программного обеспечения алгебры.
| Степень | FФ2 | F 3 | Ф 5 | FF7 |
|---|---|---|---|---|
| 1 | х + 1 | х + 1 | х + 3 | х + 4 |
| 2 | х 2 + х + 1 | х 2 + 2x + 2 | х 2 + 4 х + 2 | х 2 + 6 х + 3 |
| 3 | х 3 + х + 1 | х 3 + 2x + 1 | х 3 + 3 х + 3 | х 3 + 6x 2 + 4 |
| 4 | х 4 + х + 1 | х 4 + 2x 3 + 2 | х 4 + 4x 2 + 4 х + 2 | х 4 + 5x 2 + 4 х + 3 |
| 5 | х 5 + х 2 + 1 | х 5 + 2x + 1 | х 5 + 4 х + 3 | х 5 + х + 4 |
| 6 | х 6 + х 4 + х 3 + х + 1 | х 6 + 2x 4 + х 2 + 2x + 2 | х 6 + х 4 + 4x 3 + х 2 + 2 | х 6 + х 4 + 5x 3 + 4x 2 + 6 х + 3 |
| 7 | х 7 + х + 1 | х 7 + 2x 2 + 1 | х 7 + 3 х + 3 | х 7 + 6 х + 4 |
| 8 | х 8 + х 4 + х 3 + х 2 + 1 | х 8 + 2x 5 + х 4 + 2x 2 + 2x + 2 | х 8 + х 4 + 3x 2 + 4 х + 2 | х 8 + 4x 3 + 6x 2 + 2 х + 3 |
| 9 | х 9 + х 4 + 1 | х 9 + 2x 3 + 2x 2 + х + 1 | х 9 + 2x 3 + х + 3 | х 9 + 6x 4 + х 3 + 6 х + 4 |
Примеры
[ редактировать ]Чтобы проиллюстрировать определение, вычислим первые шесть полиномов Конвея над F 5 . По определению, полином Конвея является моническим, примитивным (что подразумевает неприводимость) и совместим с полиномами Конвея степени, делящей его степень. В таблице ниже показано, как наложение каждого из этих условий уменьшает количество полиномов-кандидатов. [8]
| Степень | Моника | нередуцируемый | примитивный | совместимый |
|---|---|---|---|---|
| 1 | 5 | 5 | 2 | 2 |
| 2 | 25 | 10 | 4 | 2 |
| 3 | 125 | 40 | 20 | 10 |
| 4 | 625 | 150 | 48 | 12 |
| 5 | 3125 | 624 | 280 | 140 |
| 6 | 15625 | 2580 | 720 | 18 |
Степень 1. Примитивными элементами F 5 являются 2 и 3. Таким образом, два полинома степени 1 с примитивными корнями равны x - 2 = x + 3 и x - 3 = x + 2 , что соответствует словам 12 и 13, Поскольку 12 меньше 13 в лексикографическом порядке, C 5,1 ( x ) = x + 3 .
Степень 2. Так как (5 2 − 1) / (5 1 − 1) = 6 , совместимость требует, чтобы C 5,2 был выбран так, чтобы C 5,2 ( x ) делил C 5,1 ( x 6 ) = х 6 + 3 . Последний факторизуется в три полинома степени 2, неприводимых над F 5 , а именно x 2 + 2 , х 2 + х + 2 и х 2 + 4 х + 2 . Из них х 2 + 2 не является примитивным, поскольку делит x 8 − 1, что означает, что его корни имеют порядок не более 8, а не требуемых 24. Оба остальных являются примитивными, и C 5,2 выбран как лексикографически меньший из двух. Теперь х 2 + х + 2 = х 2 − 4 x + 2 соответствует слову 142, а x 2 + 4 х + 2 = х 2 − x + 2 соответствует слову 112, причем последнее лексикографически меньше первого. Следовательно, C 5,2 ( x ) = x 2 + 4 х + 2 .
Степень 3. Так как (5 3 − 1) / (5 1 − 1) = 31 , совместимость требует, чтобы C 5,3 ( x ) делил C 5,1 ( x 31 ) = х 31 + 3 , который факторизует как полином степени 1, умноженный на произведение десяти примитивных полиномов степени 3. Из них два не имеют квадратичного члена x 3 + 3 х + 3 = х 3 − 0 х 2 + 3 х − 2 и х 3 + 4 х + 3 = х 3 − 0 х 2 + 4 x − 2 , которые соответствуют словам 1032 и 1042. Поскольку 1032 лексикографически меньше 1042, C 5,3 ( x ) = x 3 + 3 х + 3 .
Степень 4. Собственные делители числа 4 — 1 и 2 . Вычислить (5 4 − 1) / (5 2 − 1) = 26 и (5 4 − 1) / (5 1 − 1) = 156 и заметим, что 156/26 = (5 2 − 1) / (5 2 − 1) = 6 , тот же показатель степени, который указан в условии совместимости для степени 2. В степени 4 совместимость требует, чтобы C 5,4 был выбран так, чтобы C 5,4 ( x ) делил оба C 5,2 ( x 26 ) = х 52 + 4x 26 + 2 и С 5,1 ( х 156 ) = х 156 + 3 . Однако второе условие является избыточным, поскольку при выборе C 5,2 накладывается условие совместимости , из которого следует, что C 5,2 ( x 26 ) делит C 5,1 ( x 156 ) . В общем, для составной степени d те же рассуждения подразумевают, что необходимо рассматривать только максимальные собственные делители d , то есть делители формы d / p , где p — простой делитель d . Имеется 13 факторов C 5,2 ( x 26 ) , все степени 4. Все, кроме одного, примитивны. Из примитивных x 4 + 4x 2 + 4 x + 2 лексикографически минимально.
Степень 5. Вычисление аналогично тому, что делалось для степеней 2 и 3: (5 5 − 1) / (5 1 − 1) = 781 ; С 5,1 ( х 781 ) = х 781 +3 имеет один фактор степени 1 и 156 факторов степени 5, из них 140 примитивных. Лексикографически наименьший из примитивных множителей — это x 5 + 4 х + 3 .
Степень 6. Принимая во внимание приведенное выше обсуждение в связи со степенью 4, необходимо учитывать два условия совместимости: C 5,6 ( x ) должен делить C 5,2 ( x 651 ) = х 1302 + 4x 651 + 2 и С 5,3 ( х 126 ) = х 378 + 3x 126 + 3 . Следовательно, он должен разделить их наибольший общий делитель x 126 + х 105 + 2x 84 + 3x 42 + 2 , который разлагается на 21 многочлен 6-й степени, 18 из которых являются примитивными. Лексикографически наименьший из них — x 6 + х 4 + 4x 3 + х 2 + 2 .
Вычисление
[ редактировать ]Алгоритмы вычисления полиномов Конвея, которые более эффективны, чем поиск методом грубой силы, были разработаны Хитом и Лоером. [9] Любек указывает [5] что их алгоритм является повторным открытием метода Паркера.
Примечания
[ редактировать ]- ^ «Глава 59». Руководство по GAP 4 . Группа ГАП . Проверено 8 февраля 2011 г.
- ^ Грейсон, Дэниел Р.; Стиллман, Майкл Э. «Macaulay2, система программного обеспечения для исследований в области алгебраической геометрии» . Архивировано из оригинала 20 июля 2011 года . Проверено 29 ноября 2023 г.
- ^ Босма, В.; Стил, А. «Справочник по магме: конечные поля» . Группа вычислительной алгебры, Школа математики и статистики, Сиднейский университет . Проверено 29 ноября 2023 г.
- ^ «Таблицы Фрэнка Любека полиномов Конвея над конечными полями» . Команда разработчиков Sage . Проверено 29 ноября 2023 г.
- ^ Jump up to: Перейти обратно: а б Любек, Франк. «Полиномы Конвея для конечных полей» . Проверено 8 февраля 2011 г.
- ^ Коэффициенты C p , n для p = 2 , 3, 5, 7 и 11являются A141646 , A141647 , A141648 , A141649 и A141749 в OEIS .
- ^ Никель, Вернер (1988), Конечные поля в теоретико-групповой программной системе GAP , Дипломная работа, RWTH Aachen , получено 10 февраля 2011 г.
- ^ Есть 5 д монические многочлены степени d над F 5 . Для каждой степени количество монических неприводимых полиномов над F 5 определяется как A001692 в OEIS. Номера примитивных полиномов задаются как A027741 .
- ^ Хит, Ленвуд С.; Лоер, Николас А. (1998). «Новые алгоритмы генерации полиномов Конвея над конечными полями» . Политехнический институт Вирджинии и Государственный университет. Технический отчет ncstrl.vatech_cs//TR-98-14, Информатика . Проверено 8 февраля 2011 г.
Ссылки
[ редактировать ]- Холт, Дерек Ф.; Эйк, Беттина; О'Брайен, Имонн А. (2005), Справочник по вычислительной теории групп , Дискретная математика и ее приложения, том. 24, CRC Press, ISBN 978-1-58488-372-2