Многочлен Конвея (конечные поля)
-
Определение многочленов Конвея
- Многочлены Конвея Cp,n для конечного поля Fpn являются неприводимыми многочленами степени n от Fp.
- Они используются для определения стандартного представления Fpn как поля разделения Cp,n.
- Названы в честь Джона Х. Конвея и Ричарда А. Паркера.
-
Совместимость и представление элементов
- Многочлены Конвея удовлетворяют условию совместимости между представлениями поля и его подполей.
- Элементы Fpn могут быть представлены как суммы вида an−1βn−1 + … + a1β + a0, где β – корень неприводимого многочлена степени n от Fp.
- Примитивный элемент α из Fpn генерирует мультипликативную группу поля.
-
Выбор многочленов Конвея
- Многочлен Конвея выбирается примитивным, чтобы каждый его корень порождал мультипликативную группу поля.
- Поле Fpn содержит уникальное подполе для каждого m, делящего n.
- Многочлен Конвея для конечного поля выбирается совместимым с многочленами Конвея для его подполей.
-
Лексикографическое упорядочение
- Многочлены степени d в Fp[x] упорядочены лексикографически по словам ad ad−1 … a0.
- Лексикографическое упорядочение используется для выбора минимального многочлена, удовлетворяющего условиям совместимости.
-
Примеры вычисления многочленов Конвея
- Для F5: C5,1(x) = x + 3, C5,2(x) = x2 + 4x + 2, C5,3(x) = x3 + 3x + 3, C5,4(x) = x4 + 4×2 + 4x + 2, C5,5(x) = x5 + 4x + 3, C5,6(x) = x6 + x4 + 4×3 + x2 + 2.
-
Вычисление многочленов Конвея
- Алгоритмы вычисления многочленов Конвея разработаны Хитом и Лоэром.
- Любек указывает, что их алгоритм является повторным открытием метода Паркера.