Введение

Алгебраическая структура

В математике конечное поле или поле Галуа (названное в честь Эвариста Галуа) — это поле, содержащее конечное число элементов. Как и любое другое поле, конечное поле представляет собой множество, на котором определены операции умножения, сложения, вычитания и деления, удовлетворяющие определенным основным правилам. Наиболее распространенные примеры конечных полей даются целыми числами по модулю p, где p — простое число. Порядок конечного поля — это количество его элементов, которое является либо простым числом, либо степенью простого числа. Для каждого простого числа p и каждого положительного целого числа k существуют поля порядка p^k, все из которых изоморфны. Конечные поля играют фундаментальную роль во многих областях математики и информатики, включая теорию чисел, алгебраическую геометрию, теорию Галуа, конечную геометрию, криптографию и теорию кодирования.

Неосновные поля

При наличии простой степени 1 = q = p^(n), где p – простое число и n > 1, поле GF(q) может быть явно построено следующим образом. Сначала выбирается неприводимый многочлен P в GF(p)[X] степени n (такой неприводимый многочлен всегда существует). Тогда факторкольцо полиномиального кольца GF(p)[X] по идеалу, порожденному P, является полем порядка q. Более конкретно, элементы GF(q) – это многочлены над GF(p), степень которых строго меньше n. Сложение и вычитание выполняются как для многочленов над GF(p). Произведение двух элементов – это остаток от деления с остатком произведения в GF(p)[X] на P. Обратный к ненулевому элементу может быть вычислен с помощью расширенного алгоритма Евклида; см. Однако, при таком представлении элементы GF(q) может быть трудно отличить от соответствующих многочленов. Поэтому обычно дают имя, чаще всего α, элементу GF(q), соответствующему многочлену X. Таким образом, элементы GF(q) становятся многочленами от α, где 1 = P(α) = 0, и, когда встречается многочлен от α степени, большей или равной n (например, после умножения), необходимо использовать соотношение 1 = P(α) = 0 для понижения его степени (это и делает деление с остатком). За исключением построения GF(4), существует несколько возможных вариантов выбора P, дающих изоморфные результаты. Для упрощения деления с остатком обычно выбирают для P многочлен вида, который делает необходимые деления с остатком очень эффективными. Однако для некоторых полей, как правило, в характеристике 2, неприводимые многочлены вида X^(n) + aX + b могут не существовать. В характеристике 2, если многочлен X^(n) + X + 1 приводим, рекомендуется выбирать X^(n) + X^(k) + 1 с наименьшим возможным k, при котором многочлен становится неприводимым. Если все эти трехчлены приводимы, выбирают «пентаномы» X^(n) + X^(a) + X^(b) + X^(c) + 1, поскольку многочлены степени больше 1 с четным числом членов никогда не являются неприводимыми в характеристике 2, имея 1 в качестве корня. Возможный выбор для такого многочлена дают многочлены Конвея. Они обеспечивают определенную совместимость между представлением поля и представлениями его подполей. В следующих разделах мы покажем, как описанный выше общий метод построения работает для небольших конечных полей.

GF(p2) для нечетного простых p

Для применения вышеуказанной общей конструкции конечных полей в случае GF(p²) необходимо найти неприводимый многочлен степени 2. Для p = 2 это было сделано в предыдущем разделе. Если p – нечётное простое число, то всегда существуют неприводимые многочлены вида X² − r, где r принадлежит GF(p). Более точно, многочлен X² − r неприводим над GF(p) тогда и только тогда, когда r является квадратичным невычетом по модулю p (это почти определение квадратичного невычета). Существуют квадратичные невычеты по модулю p. Например, 2 является квадратичным невычетом для p = 3, 5, 11, 13, а 3 является квадратичным невычетом для p = 5, 7, 17. Если p ≡ 3 (mod 4), то есть p = 3, 7, 11, 19, можно выбрать −1 ≡ p − 1 в качестве квадратичного невычета, что позволяет получить очень простой неприводимый многочлен X² + 1. Выбрав квадратичный невычет r, обозначим α символическим квадратным корнем из r, то есть символом, удовлетворяющим α² = r, подобно тому, как комплексное число i является символическим квадратным корнем из −1. Тогда элементы GF(p²) – это все линейные выражения вида a + bα, где a и b принадлежат GF(p). Операции в GF(p²) определяются следующим образом (операции между элементами GF(p), представленными латинскими буквами, являются операциями в GF(p)):

Множительная структура

Множество ненулевых элементов в GF(q) является абелевой группой относительно умножения, порядок которой равен q – 1. По теореме Лагранжа, существует делитель k числа q – 1, такой что x^(k) = 1 для каждого ненулевого x в GF(q). Поскольку уравнение x^(k) = 1 имеет не более k решений в любом поле, q – 1 является наименьшим возможным значением для k. Теорема о структуре конечных абелевых групп подразумевает, что эта мультипликативная группа является циклической, то есть все ненулевые элементы являются степенями одного элемента. Вкратце:

Такой элемент a называется примитивным элементом GF(q). Если q не равно 2 или 3, то примитивный элемент не является единственным. Число примитивных элементов равно φ(q − 1), где φ – функция Эйлера. Из вышесказанного следует, что x^(q) = x для каждого x в GF(q). Частный случай, когда q является простым числом, известен как малая теорема Ферма.

Корни единства

Каждый ненулевой элемент конечного поля является корнем из единицы, так как 1 = x^(q−1) = 1 для каждого ненулевого элемента GF(q). Если n – положительное целое число, то n-й первообразный корень единицы является решением уравнения 1 = x^n = 1, которое не является решением уравнения 1 = x^m = 1 для любого положительного целого числа m < n. Если a – n-й первообразный корень единицы в поле F, то F содержит все n корней единицы, то есть 1, a, a^2, ..., a^(n−1). Поле GF(q) содержит n-й первообразный корень единицы тогда и только тогда, когда n является делителем q − 1; если n является делителем q − 1, то число первообразных n-х корней единицы в GF(q) равно φ(n) (функция Эйлера). Число n-х корней единицы в GF(q) равно НОД(n, q − 1). В поле характеристики p каждый (np)-й корень единицы также является n-м корнем единицы. Следовательно, первообразные (np)-е корни единицы не существуют в поле характеристики p.

С другой стороны, если n взаимно просто с p, корни n-го циклотомического многочлена различны в каждом поле характеристики p, поскольку этот многочлен является делителем X^n − 1, чей дискриминант n^n отличен от нуля по модулю p. Следовательно, n-й циклотомический многочлен разлагается над GF(p) на различные неприводимые многочлены, имеющие одинаковую степень, скажем d, и GF(p^d) является наименьшим полем характеристики p, содержащим n-е первообразные корни единицы.

Факторизация многочлена

Если F — конечное поле, то моничный полином с коэффициентами в F, не являющийся константой, называется неприводимым над F, если он не может быть представлен в виде произведения двух моничных полиномов с коэффициентами в F, не являющихся константами.

Поскольку каждое кольцо многочленов над полем является областью однозначной факторизации, каждый моничный полином над конечным полем может быть однозначно (с точностью до порядка сомножителей) разложен на произведение неприводимых моничных полиномов. Существуют эффективные алгоритмы для проверки неприводимости многочлена и факторизации многочленов над конечными полями. Они являются ключевым этапом при факторизации многочленов над целыми числами или рациональными числами. По крайней мере, по этой причине, каждая система компьютерной алгебры имеет функции для факторизации многочленов над конечными полями или, по крайней мере, над конечными простыми полями.

Приложения

В криптографии сложность задачи дискретного логарифмирования в конечных полях или на эллиптических кривых является основой нескольких широко используемых протоколов, таких как протокол Диффи — Хеллмана. Например, в 2014 году безопасное интернет-соединение с Википедией использовало протокол Диффи — Хеллмана на эллиптических кривых (ECDHE) над большим конечным полем. В теории кодирования многие коды строятся как подпространства векторных пространств над конечными полями. Конечные поля используются во многих кодах коррекции ошибок, таких как код Рида — Соломона или код БЧ. Конечные поля почти всегда имеют характеристику 2, поскольку компьютерные данные хранятся в двоичном формате. Например, байт данных можно интерпретировать как элемент GF(2⁸). Исключением является штрих-код PDF417, который использует GF(929). Некоторые процессоры имеют специальные инструкции, полезные для конечных полей характеристики 2, как правило, варианты умножения без переноса. Конечные поля широко используются в теории чисел, поскольку многие задачи, сформулированные для целых чисел, можно решить, приводя их по модулю одного или нескольких простых чисел. Например, самые быстрые известные алгоритмы для факторизации многочленов и линейной алгебры над полем рациональных чисел работают путем приведения по модулю одного или нескольких простых чисел, а затем восстановления решения с использованием китайской теоремы об остатках, подъема Хенселя или алгоритма LLL. Аналогично, многие теоретические задачи в теории чисел можно решить, рассматривая их приведения по модулю некоторых или всех простых чисел. См., например, принцип Хассе. Многие недавние достижения в алгебраической геометрии были мотивированы необходимостью расширить возможности этих модульных методов. Доказательство Уайлса последней теоремы Ферма является примером глубокого результата, использующего множество математических инструментов, включая конечные поля. Предположения Вейля касаются числа точек на алгебраических многообразиях над конечными полями, и эта теория имеет множество применений, включая оценки экспоненциальных и сумм характеров. Конечные поля широко применяются в комбинаторике, два известных примера — определение графов Пейли и связанная с ними конструкция матриц Адамара. В арифметической комбинаторике конечные поля и модели конечных полей широко используются, например, в теореме Сземереди о арифметических прогрессиях.

Маленькая теорема Уэддерберна

Раздельное кольцо является обобщением понятия поля. Не предполагается, что раздельные кольца коммутативны. Некоммутативных конечных раздельных колец не существует: малая теорема Уэддерберна утверждает, что все конечные раздельные кольца коммутативны и, следовательно, являются конечными полями. Этот результат справедлив даже в случае ослабления аксиомы ассоциативности до альтернативности, то есть все конечные альтернативные раздельные кольца являются конечными полями, согласно теореме Артина — Зорна.

Квазиалгебраическое закрытие

Хотя конечные поля не являются алгебраически замкнутыми, они квазиалгебраически замкнуты, что означает, что каждый однородный многочлен над конечным полем имеет нетривиальный корень, координаты которого принадлежат этому полю, если число переменных больше степени многочлена. Это была гипотеза Артина и Диксона, доказанная Шевалье (см. теорему Шевалье — Предупреждения).