Полином Конвея (конечные поля)

Единообразное кодирование примитивных элементов всех конечных полей

В математике многочлен Конвея $C p, n$ для конечного поля $F p n$ является частным неприводимым многочленом степени $n$ над $F p ,$ который может быть использован для определения стандартного представления $F p n$ как поля разбиения $C$ p $,$ $n$ . Многочлены Конвея были названы в честь Джона Х. Конвея Ричардом А. Паркером , который первым определил их и вычислил примеры. Многочлены Конвея $удовлетворяют$ определенному условию совместимости, которое было предложено Конвеем между представлением поля и представлениями его подполей. Они важны в компьютерной алгебре , где они обеспечивают переносимость между различными математическими базами данных и системами компьютерной алгебры. Поскольку многочлены Конвея дороги для вычисления, их необходимо хранить для использования на практике. Базы данных полиномов Конвея доступны в системах компьютерной алгебры GAP , ^[1] Macaulay2 , ^[2] Magma , ^[3] SageMath , ^[4] на веб-сайте Франка Любека, ^[5] и в Онлайн-энциклопедии целочисленных последовательностей . ^[6]

Фон

Элементы $F p n$ могут быть представлены в виде сумм вида $a n -1 β n -1 + \dots + a 1 β + a 0$ , где $β$ — корень неприводимого многочлена степени $n$ над $F p$ , а $a j$ — элементы $F p$ . Сложение элементов поля в этом представлении — это просто сложение векторов. Хотя существует единственное конечное поле порядка $p n$ с точностью до изоморфизма , представление элементов поля зависит от выбора неприводимого многочлена. Многочлен Конвея — это способ стандартизации этого выбора.

Ненулевые элементы конечного поля $F$ образуют циклическую группу относительно умножения, обозначаемую $F *$ . Примитивный элемент , $α$ , поля $F p n$ является элементом, который порождает $F * p n$ . Представление ненулевых элементов поля в виде степеней $α$ позволяет эффективно выполнять умножение в поле. Примитивный многочлен для $α$ является моническим многочленом наименьшей возможной степени с коэффициентами в $F p$ , имеющим $α$ в качестве корня в $F p n$ ( минимальный многочлен для $α$ ). Он обязательно неприводим. Многочлен Конвея выбирается примитивным, так что каждый из его корней порождает мультипликативную группу соответствующего конечного поля.

Поле $F p n$ содержит единственное подполе, изоморфное $F p m$ для каждого $m,$ делящего $n$ , и это учитывает все подполя $F p n$ . Для любого $m,$ делящего $n,$ циклическая группа $F * p n$ содержит подгруппу, изоморфную $F * p m$ . Если $α$ порождает $F * p n$ , то наименьшая степень $α$ , которая порождает эту подгруппу, равна $α r$ , где $r = (p n - 1) / (p m - 1)$ . Если $f n$ — примитивный многочлен для $F p n$ с корнем $α$ , а $f m$ — примитивный многочлен для $F p m,$ то, по определению Конвея, $f m$ и $f n$ совместимы , если $α r$ — корень $f m$ . Это требует, чтобы $f n (x)$ делило $f m (x r)$ . Это понятие совместимости некоторые авторы называют совместимостью с нормой . Полином Конвея для конечного поля выбирается так, чтобы быть совместимым с полиномами Конвея каждого из его подполей. То, что выбор можно сделать таким образом, было доказано Вернером Никелем. ^[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 < \dots < p - 1$ .
Многочлен степени $d$ в $F p [x]$ записывается $как a d x d - a d -1 x d -1 + \dots + (-1) d a 0$ (с попеременным добавлением и вычитанием членов) и затем выражается как слово $a d a d -1 \dots a 0$ . Два многочлена степени d упорядочены в соответствии с лексикографическим порядком соответствующих им слов.

Поскольку, по-видимому, не существует естественного математического критерия, который бы выделял один монический примитивный многочлен, удовлетворяющий условиям совместимости среди всех остальных, введение лексикографического упорядочения в определении многочлена Конвея следует рассматривать как соглашение.

Стол

Полиномы Конвея $C p, n$ для наименьших значений $p$ и $n$ приведены в таблице ниже. Все они были впервые вычислены Ричардом Паркером и взяты из таблиц Фрэнка Любека. Вычисления можно проверить, используя основные методы следующего раздела с помощью алгебраического программного обеспечения.

Полиномы Конвея над $F p$ для малых $p$ и малых степеней.
Степень	$Ф 2$	$Ф 3$	$Ф 5$	$Ф 7$
1	$х + 1$	$х + 1$	$х + 3$	$х + 4$
2	$х 2 + х + 1$	$х 2 + 2 х + 2$	$х 2 + 4 х + 2$	$х 2 + 6 х + 3$
3	$х 3 + х + 1$	$х 3 + 2 х + 1$	$х 3 + 3 х + 3$	$х 3 + 6 х 2 + 4$
4	$х 4 + х + 1$	$х 4 + 2 х 3 + 2$	$х 4 + 4 х 2 + 4 х + 2$	$х 4 + 5 х 2 + 4 х + 3$
5	$х 5 + х 2 + 1$	$х 5 + 2 х + 1$	$х 5 + 4 х + 3$	$х 5 + х + 4$
6	$х 6 + х 4 + х 3 + х + 1$	$х 6 + 2 х 4 + х 2 + 2 х + 2$	$х 6 + х 4 + 4 х 3 + х 2 + 2$	$х 6 + х 4 + 5 х 3 + 4 х 2 + 6 х + 3$
7	$х 7 + х + 1$	$х 7 + 2 х 2 + 1$	$х 7 + 3 х + 3$	$х 7 + 6 х + 4$
8	$х 8 + х 4 + х 3 + х 2 + 1$	$х 8 + 2 х 5 + х 4 + 2 х 2 + 2 х + 2$	$х 8 + х 4 + 3 х 2 + 4 х + 2$	$х 8 + 4 х 3 + 6 х 2 + 2 х + 3$
9	$х 9 + х 4 + 1$	$х 9 + 2 х 3 + 2 х 2 + х + 1$	$х 9 + 2 х 3 + х + 3$	$х 9 + 6 х 4 + х 3 + 6 х + 4$

Примеры

Чтобы проиллюстрировать определение, давайте вычислим первые шесть полиномов Конвея над $F 5$ . По определению полином Конвея является моническим, примитивным (что подразумевает неприводимость) и совместимым с полиномами Конвея степени, делящей его степень. Таблица ниже показывает, как наложение каждого из этих условий уменьшает количество кандидатов на полиномы. ^[8]

Числа кандидатов-полиномов над $F 5$ накладываются в качестве последовательных условий.
Степень	моник	неприводимый	примитивный	совместимый
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) = x 6 + 3$ . Последний факторизуется в три многочлена степени 2, неприводимых над $F 5$ , а именно $x 2 + 2$ , $x 2 + x + 2$ и $x 2 + 4 x + 2$ . Из них $x 2 + 2$ не является примитивным, поскольку он делит $x 8 - 1$ , что подразумевает, что его корни имеют порядок не более 8, а не требуемые 24. Оба других являются примитивными, и $C 5,2$ выбирается как лексикографически меньший из двух. Теперь $x 2 + x + 2 = x 2 - 4 x + 2$ соответствует слову 142, а $x 2 + 4 x + 2 = x 2 - x + 2$ соответствует слову 112, причем последнее лексикографически меньше первого. Следовательно, $C 5,2 (x) = x 2 + 4 x + 2$ .

Степень 3. Поскольку $(5 3 - 1) / (5 1 - 1) = 31$ , совместимость требует, чтобы $C 5,3 (x)$ делило $C 5,1 (x 31) = x 31 + 3$ , что факторизуется как многочлен степени 1, умноженный на произведение десяти примитивных многочленов степени 3. Из них два не имеют квадратичного члена, $x 3 + 3 x + 3 = x 3 - 0 x 2 + 3 x - 2$ и $x 3 + 4 x + 3 = x 3 - 0 x 2 + 4 x - 2$ , что соответствует словам 1032 и 1042. Поскольку 1032 лексикографически меньше 1042, $C 5,3 (x) = x 3 + 3 x + 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) = x 52 + 4 x 26 + 2$ , так и $C 5,1 (x 156) = x 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 + 4 x 2 + 4 x + 2$ является лексикографически минимальным.

Степень 5. Вычисление аналогично тому, что было сделано в степенях 2 и 3: $(5 5 - 1) / (5 1 - 1) = 781$ ; $C 5,1 (x 781) = x 781 + 3$ имеет один множитель степени 1 и 156 множителей степени 5, из которых 140 являются примитивными. Лексикографически наименьшим из примитивных множителей является $x 5 + 4 x + 3$ .

Степень 6. Принимая во внимание обсуждение выше в связи со степенью 4, два условия совместимости, которые необходимо рассмотреть, заключаются в том, что $C 5,6 (x)$ должно делить $C 5,2 (x 651) = x 1302 + 4 x 651 + 2$ и $C 5,3 (x 126) = x 378 + 3 x 126 + 3$ . Следовательно, оно должно делить их наибольший общий делитель $x 126 + x 105 + 2 x 84 + 3 x 42 + 2$ , который раскладывается на 21 многочлен степени 6, 18 из которых являются примитивными. Лексикографически наименьшим из них является $x 6 + x 4 + 4 x 3 + x 2 + 2$ .

Вычисление

Хитом и Лёром были разработаны алгоритмы вычисления полиномов Конвея, которые более эффективны, чем поиск методом грубой силы. ^[9] Любек указывает ^[5] , что их алгоритм является повторным открытием метода Паркера.

Примечания

^ "Глава 59". Руководство GAP 4. Группа GAP . Получено 8 февраля 2011 г.
^ Грейсон, Дэниел Р.; Стиллман, Майкл Э. «Macaulay2, программная система для исследований в области алгебраической геометрии». Архивировано из оригинала 20 июля 2011 г. Получено 29 ноября 2023 г.
^ Bosma, W.; Steel, A. "Magma handbook: final fields". Computational Algebra Group, School of Mathematics and Statistics, University of Sydney . Получено 29 ноября 2023 г.
^ "Таблицы Франка Любека полиномов Конвея над конечными полями". The Sage Development Team . Получено 29 ноября 2023 г.
^ ab Lübeck, Frank. "Conway polynomials for final fields" . Получено 8 февраля 2011 г. .
^ Коэффициенты $C p, n$ для $p = 2$ , 3, 5, 7 и 11 равны A141646, A141647, A141648, A141649 и A141749 в OEIS .
^ Никель, Вернер (1988), Endliche Körper in dem gruppentheoretischen Programmsystem GAP, дипломная работа, RWTH Aachen , получено 10 февраля 2011 г..
^ Существует $5 d$ монических многочленов степени $d$ над $F 5$ . Для каждой степени число монических неприводимых многочленов над $F 5$ задается как A001692 в OEIS. Число примитивных многочленов задается как A027741.
^ Хит, Ленвуд С.; Лоэр, Николас А. (1998). «Новые алгоритмы генерации полиномов Конвея над конечными полями». Политехнический институт и государственный университет Вирджинии. Технический отчет ncstrl.vatech_cs//TR-98-14, Computer Science . Получено 8 февраля 2011 г.

Ссылки

Холт, Дерек Ф.; Эйк, Беттина; О'Брайен, Имонн А. (2005), Справочник по вычислительной теории групп , Дискретная математика и ее приложения, т. 24, CRC Press, ISBN 978-1-58488-372-2

[1] "Глава 59". Руководство GAP 4. Группа GAP . Получено 8 февраля 2011 г.

[2] Грейсон, Дэниел Р.; Стиллман, Майкл Э. «Macaulay2, программная система для исследований в области алгебраической геометрии». Архивировано из оригинала 20 июля 2011 г. Получено 29 ноября 2023 г.

[3] Bosma, W.; Steel, A. "Magma handbook: final fields". Computational Algebra Group, School of Mathematics and Statistics, University of Sydney . Получено 29 ноября 2023 г.

[4] "Таблицы Франка Любека полиномов Конвея над конечными полями". The Sage Development Team . Получено 29 ноября 2023 г.

[FOOTNOTESLuebeck-5] Lübeck, Frank. "Conway polynomials for final fields" . Получено 8 февраля 2011 г. .

[6] Коэффициенты $C p, n$ для $p = 2$ , 3, 5, 7 и 11 равны A141646, A141647, A141648, A141649 и A141749 в OEIS .

[7] Никель, Вернер (1988), Endliche Körper in dem gruppentheoretischen Programmsystem GAP, дипломная работа, RWTH Aachen , получено 10 февраля 2011 г..

[8] Существует $5 d$ монических многочленов степени $d$ над $F 5$ . Для каждой степени число монических неприводимых многочленов над $F 5$ задается как A001692 в OEIS. Число примитивных многочленов задается как A027741.

[9] Хит, Ленвуд С.; Лоэр, Николас А. (1998). «Новые алгоритмы генерации полиномов Конвея над конечными полями». Политехнический институт и государственный университет Вирджинии. Технический отчет ncstrl.vatech_cs//TR-98-14, Computer Science . Получено 8 февраля 2011 г.