Конечное поле - Finite field

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

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

Характеристики

Конечное поле - это конечное множество, которое является полем ; это означает, что умножение, сложение, вычитание и деление (исключая деление на ноль) определены и удовлетворяют правилам арифметики, известным как аксиомы поля .

Количество элементов конечного поля называется его порядком , а иногда и размером . Конечное поле порядка q существует тогда и только тогда, когда q - степень простого числа p ^k (где p - простое число, а k - положительное целое число). В поле порядка p ^k добавление p копий любого элемента всегда приводит к нулю; то есть характеристика поля равна p .

Если д = р ^к , все поля порядка ц являются изоморфными (см § Существование и единственность ниже). Более того, поле не может содержать два разных конечных подполя с одинаковым порядком. Поэтому можно определить все конечные поля с тем же порядком, и они однозначно обозначены , F _д или GF ( д ) , где буквы GF стоять «поле Галуа». ${\ displaystyle \ mathbb {F} _ {q}}$

В конечном поле порядка q у многочлена X ^q - X все q элементов конечного поля являются корнями . Ненулевые элементы конечного поля образуют мультипликативную группу . Эта группа является циклической , поэтому все ненулевые элементы могут быть выражены как степени одного элемента, называемого примитивным элементом поля. (Как правило, для данного поля будет несколько примитивных элементов.)

Простейшие примеры конечных полей являются полями простого порядка: для каждого простого числа р , с простым полем порядка р , можно построить как целые числа по модулю р , Z / р Z . ${\ displaystyle \ mathbb {F} _ {p}}$

Элементы простого поля порядка p могут быть представлены целыми числами в диапазоне 0, ..., p - 1 . Сумма, разность и произведение - это остаток от деления на p результата соответствующей целочисленной операции. Мультипликативный обратный элемент может быть вычислен с помощью расширенного алгоритма Евклида (см. Расширенный алгоритм Евклида § Модульные целые числа ).

Пусть F - конечное поле. Для любого элемента x в F и любого целого числа n обозначим через n ⋅ x сумму n копий x . Наименьшее положительное n такое, что n ⋅ 1 = 0, является характеристикой поля p . Это позволяет определить умножение элемента k из GF ( p ) на элемент x из F , выбрав целое число, представляющее k . Это умножение превращает F в GF ( p ) - векторное пространство . Отсюда следует, что количество элементов F равно p ⁿ для некоторого целого n . ${\ Displaystyle (к, х) \ mapsto к \ cdot x}$

идентичность

${\ displaystyle (x + y) ^ {p} = x ^ {p} + y ^ {p}}$

(иногда называемое мечтой первокурсника ) истинно в области характеристики p . Это следует из биномиальной теоремы , поскольку каждый биномиальный коэффициент разложения ( x + y ) ^p , кроме первого и последнего, кратен p .

По малой теореме Ферма , если p - простое число и x находится в поле GF ( p ), то x ^p = x . Отсюда следует равенство

${\ Displaystyle X ^ {p} -X = \ prod _ {a \ in {\ rm {GF}} (p)} (Xa)}$

для многочленов над GF ( p ) . В более общем смысле, каждый элемент в GF ( p ⁿ ) удовлетворяет полиномиальному уравнению x ^{p n} - x = 0 .

Любое конечное расширение конечного поля отделимо и просто. То есть, если E - конечное поле, а F - подполе E , то E получается из F присоединением одного элемента, минимальный многочлен которого отделим. Выражаясь жаргоном, конечные поля идеальны .

Более общая алгебраическая структура, которая удовлетворяет всем другим аксиомам поля, но чье умножение не требуется, чтобы быть коммутативным, называется телом (или иногда телом ). По малой теореме Веддерберна любое конечное тело коммутативно и, следовательно, является конечным полем.

Существование и уникальность

Пусть q = p ⁿ - степень простого числа , а F - поле расщепления многочлена

${\ displaystyle P = X ^ {q} -X}$

над простым полем GF ( p ) . Это означает , что Р представляет собой конечное поле низшего порядка, в котором Р имеет Q различные корни (далее формальной производной от Р является Р ' = -1 , подразумевая , что НОД ( P , P ' ) = 1 , что в целом означает , что поле расщепления является отделимым расширением оригинала). В выше идентичности показывает , что сумма и произведение двух корней P являются корнями Р , а также мультипликативный обратный корень P . Другими словами, корни P образуют поле порядка q , которое равно F по минимальности поля расщепления.

Из единственности с точностью до изоморфизма полей расщепления следует, что все поля порядка q изоморфны. Кроме того, если поле F имеет поле порядка q = p ^k в качестве подполя, его элементы являются q корнями X ^q - X , и F не может содержать другое подполе порядка q .

Таким образом, мы имеем следующую классификационную теорему, впервые доказанную в 1893 году Э. Муром :

Порядок конечного поля - это степень простого числа. Для каждой степени q простого числа существуют поля порядка q , и все они изоморфны. В этих полях каждый элемент удовлетворяет

${\ Displaystyle х ^ {q} = х,}$

а многочлен X ^q - X множится как

${\ displaystyle X ^ {q} -X = \ prod _ {a \ in F} (Xa).}$

Отсюда следует, что GF ( p ⁿ ) содержит подполе, изоморфное GF ( p ^m ), тогда и только тогда, когда m является делителем n ; в этом случае это подполе уникально. Фактически, многочлен X ^{p m} - X делит X ^{p n} - X тогда и только тогда, когда m является делителем n .

Явная конструкция

Непростые поля

Принимая во внимание степень простого числа д = р ^п с р простого и п > 1 , то поле GF ( Q ) может быть явно построена следующим образом. Сначала выбирается неприводимый многочлен P в GF ( p ) [ X ] степени n (такой неприводимый многочлен всегда существует). Тогда факторкольцо

${\ Displaystyle {\ rm {GF}} (q) = {\ rm {GF}} (p) [X] / (P)}$

кольца многочленов GF ( p ) [ X ] идеалом, порожденным P, является полем порядка q .

Более точно, элементы GF ( q ) - это многочлены над GF ( p ) , степень которых строго меньше n . Сложение и вычитание относятся к полиномам над GF ( p ) . Произведение двух элементов - это остаток от евклидова деления на P произведения в GF ( p ) [ X ] . Мультипликативная обратная величина ненулевого элемента может быть вычислена с помощью расширенного алгоритма Евклида; см. Расширенный алгоритм Евклида § Простые расширения алгебраических полей .

За исключением конструкции GF (4) , существует несколько возможных вариантов выбора P , которые приводят к изоморфным результатам. Чтобы упростить евклидово деление, для P обычно выбирают многочлены вида

${\ displaystyle X ^ {n} + aX + b,}$

которые делают необходимые евклидовы деления очень эффективными. Однако для некоторых полей, обычно с характеристикой 2 , неприводимые многочлены вида X ⁿ + aX + b могут не существовать. В характеристике 2 , если многочлен X ⁿ + X + 1 приводим, рекомендуется выбирать X ⁿ + X ^k + 1 с наименьшим возможным k, что делает многочлен неприводимым. Если все эти трехчлены приводимы, выбираются «пятичлены» X ⁿ + X ^a + X ^b + X ^c + 1 , поскольку многочлены степени выше 1 с четным числом членов никогда не являются неприводимыми в характеристике 2 , имеющей 1 как корень.

Возможный выбор такого многочлена дается многочленами Конвея . Они обеспечивают определенную совместимость между представлением поля и представлениями его подполей.

В следующих разделах мы покажем, как описанный выше общий метод построения работает для малых конечных полей.

Поле с четырьмя элементами

Наименьшее непростое поле - это поле с четырьмя элементами, которое обычно обозначается GF (4) или оно состоит из четырех элементов , так что и для всех остальных результатов операции легко выводятся из закона распределения . См. Ниже полные таблицы операций. ${\ displaystyle \ mathbb {F} _ {4}.}$${\ Displaystyle 0,1, \ альфа, 1 + \ альфа}$${\ Displaystyle \ альфа ^ {2} = 1 + \ альфа,}$ ${\ Displaystyle 1 \ CDOT \ альфа = \ альфа \ CDOT 1 = \ альфа,}$ ${\ Displaystyle х + х = 0,}$${\ Displaystyle х \ cdot 0 = 0 \ cdot x = 0,}$${\ Displaystyle х \ in \ OperatorName {GF} (4),}$

Это можно вывести следующим образом из результатов предыдущего раздела.

Над GF (2) имеется только один неприводимый многочлен степени2 :

${\ displaystyle X ^ {2} + X + 1}$

Следовательно, для GF (4) конструкция предыдущего раздела должна включать этот многочлен, и

${\ displaystyle {\ rm {GF}} (4) = {\ rm {GF}} (2) [X] / (X ^ {2} + X + 1).}$

Обозначим через α корень этого многочлена в GF (4) . Это означает, что

α ² = 1 + α ,

и что α и 1 + α - элементы GF (4) , не входящие в GF (2) . Таблицы операций в GF (4) являются результатом этого и выглядят следующим образом:

Сложение x + y	Умножение x ⋅ y	Деление x / y
х ╲ у 0 1 α 1 + α 0 0 1 α 1 + α 1 1 0 1 + α α α α 1 + α 0 1 1 + α 1 + α α 1 0	х ╲ у 0 1 α 1 + α 0 0 0 0 0 1 0 1 α 1 + α α 0 α 1 + α 1 1 + α 0 1 + α 1 α	х ╲ у 1 α 1 + α 0 0 0 0 1 1 1 + α α α α 1 1 + α 1 + α 1 + α α 1

Таблица для вычитания не приводится, потому что вычитание идентично сложению, как в случае с каждым полем характеристики 2. В третьей таблице для деления x на y значения x должны быть прочитаны в левом столбце. , а значения y в верхней строке. (Поскольку 0 ⋅ г = 0 для каждого г в каждом кольце деление на 0 должно оставаться неопределенным.)

Карта

${\ Displaystyle \ varphi: х \ mapsto x ^ {2}}$

- нетривиальный полевой автоморфизм, называемый автоморфизмом Фробениуса , который переводит α во второй корень 1 + α упомянутого выше неприводимого многочлена${\ displaystyle X ^ {2} + X + 1.}$

GF ( p ² ) для нечетного простого числа p

Чтобы применить приведенную выше общую конструкцию конечных полей в случае GF ( p ² ) , нужно найти неприводимый многочлен степени 2. Для p = 2 это было сделано в предыдущем разделе. Если p - нечетное простое число, всегда существуют неприводимые многочлены вида X ² - r с r в GF ( p ) .

Точнее, многочлен X ² - r неприводим над GF ( p ) тогда и только тогда, когда r - квадратичный невычет по модулю p (это почти определение квадратичного невычета). Есть п - 1/2квадратичные невычеты по модулю p . Так , например, 2 является квадратичным невычетом для р = 3, 5, 11, 13, ... , и 3 является квадратичным невычетом для р = 5, 7, 17, ... . Если p ≡ 3 mod 4 , то есть p = 3, 7, 11, 19, ... , можно выбрать −1 ≡ p - 1 в качестве квадратичного невычета, что позволяет нам иметь очень простой неприводимый многочлен X ² + 1 .

Выбрав квадратичный невычет r , пусть α будет символическим квадратным корнем из r , то есть символом, обладающим свойством α ² = r , точно так же, как комплексное число i является символическим квадратным корнем из −1 . Тогда элементами GF ( p ² ) будут все линейные выражения

${\ displaystyle a + b \ alpha,}$

с a и b в GF ( p ) . Операции на GF ( p ² ) определяются следующим образом (операции между элементами GF ( p ), представленными латинскими буквами, являются операциями в GF ( p ) ):

${\ displaystyle {\ begin {align} - (a + b \ alpha) & = - a + (- b) \ alpha \\ (a + b \ alpha) + (c + d \ alpha) & = (a + c ) + (b + d) \ alpha \\ (a + b \ alpha) (c + d \ alpha) & = (ac + rbd) + (ad + bc) \ alpha \\ (a + b \ alpha) ^ {-1} & = a (a ^ {2} -rb ^ {2}) ^ {- 1} + (- b) (a ^ {2} -rb ^ {2}) ^ {- 1} \ alpha \ конец {выровнено}}}$

GF (8) и GF (27)

Полином

${\ displaystyle X ^ {3} -X-1}$

неприводимо над GF (2) и GF (3) , т. е. неприводимо по модулю 2 и 3 (чтобы показать это, достаточно показать, что у него нет корня ни в GF (2), ни в GF (3) ). Отсюда следует, что элементы GF (8) и GF (27) могут быть представлены выражениями

${\ Displaystyle а + б \ альфа + с \ альфа ^ {2},}$

где a , b , c - элементы GF (2) или GF (3) (соответственно), и - такой символ, что ${\ displaystyle \ alpha}$

${\ displaystyle \ alpha ^ {3} = \ alpha +1.}$

Таким образом, сложение, аддитивное обратное и умножение на GF (8) и GF (27) можно определить следующим образом; в следующих формулах операции между элементами GF (2) или GF (3) , обозначенными латинскими буквами, являются операциями в GF (2) или GF (3) соответственно:

${\ displaystyle {\ begin {align} - (a + b \ alpha + c \ alpha ^ {2}) & = - a + (- b) \ alpha + (- c) \ alpha ^ {2} \ qquad {\ text {(for}} \ mathrm {GF} (8), {\ text {эта операция является тождеством)}} \\ (a + b \ alpha + c \ alpha ^ {2}) + (d + e \ альфа + е \ альфа ^ {2}) & = (а + г) + (б + е) \ альфа + (с + е) \ альфа ^ {2} \\ (а + б \ альфа + с \ альфа ^ {2}) (d + e \ alpha + f \ alpha ^ {2}) & = (ad + bf + ce) + (ae + bd + bf + ce + cf) \ alpha + (af + be + cd + ср) \ альфа ^ {2} \ конец {выровнено}}}$

GF (16)

Полином

${\ displaystyle X ^ {4} + X + 1}$

неприводимо над GF (2) , т. е. неприводимо по модулю 2 . Отсюда следует, что элементы GF (16) могут быть представлены выражениями

${\ Displaystyle а + б \ альфа + с \ альфа ^ {2} + d \ альфа ^ {3},}$

где a , b , c , d равны 0 или 1 (элементы GF (2) ), а α - такой символ, что

${\ Displaystyle \ альфа ^ {4} = \ альфа +1}$

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

${\ displaystyle {\ begin {align} (a + b \ alpha + c \ alpha ^ {2} + d \ alpha ^ {3}) + (e + f \ alpha + g \ alpha ^ {2} + h \ альфа ^ {3}) & = (a + e) ​​+ (b + f) \ alpha + (c + g) \ alpha ^ {2} + (d + h) \ alpha ^ {3} \\ (a + b \ alpha + c \ alpha ^ {2} + d \ alpha ^ {3}) (e + f \ alpha + g \ alpha ^ {2} + h \ alpha ^ {3}) & = (ae + bh + cg + df) + (af + be + bh + cg + df + ch + dg) \ alpha \; + \\ & \ quad \; (ag + bf + ce + ch + dg + dh) \ alpha ^ {2 } + (ah + bg + cf + de + dh) \ alpha ^ {3} \ end {выровнено}}}$

Мультипликативная структура

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

Мультипликативная группа ненулевых элементов в GF ( q ) является циклической, и существует такой элемент a , что q - 1 ненулевых элементов GF ( q ) являются a , a ² , ..., a ^{q −2} , a ^{q −1} = 1 .

Такой элемент а называется примитивным элементом . Если q = 2, 3 , примитивный элемент не уникален. Количество примитивных элементов равно φ ( q - 1), где φ - функция Эйлера .

Из приведенного выше результата следует, что x ^q = x для любого x в GF ( q ) . Частным случаем простого числа q является малая теорема Ферма .

Дискретный логарифм

Если a - примитивный элемент в GF ( q ) , то для любого ненулевого элемента x в F существует единственное целое число n с 0 ≤ n ≤ q - 2 такое, что

х = а ^п .

Это целое число n называется дискретным логарифмом числа x по основанию a .

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

Когда ненулевые элементы GF ( q ) представлены их дискретными логарифмами, умножение и деление просты, поскольку они сводятся к сложению и вычитанию по модулю q - 1 . Однако сложение сводится к вычислению дискретного логарифма a ^m + a ⁿ . Личность

а ^м + а ^п = а ^п ( а ^{м - п} + 1)

позволяет решить эту проблему путем построения таблицы дискретных логарифмов в ^п + 1 , называется логарифмы Зах в , для п = 0, ..., д - 2 (удобно определить дискретный логарифм нуля как - ∞ ).

Логарифмы Зеха полезны для больших вычислений, таких как линейная алгебра над полями среднего размера, то есть поля, которые достаточно велики, чтобы сделать естественные алгоритмы неэффективными, но не слишком большими, поскольку необходимо предварительно вычислить таблицу того же размера. как порядок полей.

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

Каждый ненулевой элемент конечного поля является корнем из единицы , так как x ^{q −1} = 1 для любого ненулевого элемента GF ( q ) .

Если n - положительное целое число, n- й примитивный корень из единицы является решением уравнения x ⁿ = 1 , которое не является решением уравнения x ^m = 1 для любого положительного целого числа m < n . Если a является n- м примитивным корнем из единицы в поле F , то F содержит все n корней из единицы, которые равны 1, a , a ² , ..., a ^{n −1} .

Поле GF ( q ) содержит n- й первообразный корень из единицы тогда и только тогда, когда n является делителем q - 1 ; если n является делителем q - 1 , то количество примитивных корней n- й степени из единицы в GF ( q ) равно φ ( n ) ( функция Эйлера ). Количество корней n- й степени из единицы в GF ( q ) равно gcd ( n , q - 1) .

В поле характеристики p каждый корень ( np ) -й степени из единицы также является корнем n- й степени из единицы. Отсюда следует, что примитивные ( np ) -ые корни из единицы никогда не существуют в поле характеристики p .

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

Пример: GF (64)

Поле GF (64) имеет несколько интересных свойств, которые не разделяются полями меньшего размера: у него есть два подполя, и ни одно из них не содержится в другом; не все образующие (элементы с минимальным многочленом степени 6 над GF (2) ) являются примитивными элементами; и примитивные элементы не все сопряжены относительно группы Галуа .

Порядок этого поля будучи 2 ⁶ , и делители 6 быть 1, 2, 3, 6 , подполя GF (64) являются GF (2) , GF (2 ² ) = GF (4) , Г. Ф. (2 ³ ) = GF (8) , а сам GF (64) . В 2 и 3 являются взаимно простыми , пересечение GF (4) и GF (8) в GF (64) представляет собой простое поле GF (2) .

Таким образом, объединение GF (4) и GF (8) имеет 10 элементов. Оставшиеся 54 элемента GF (64) порождают GF (64) в том смысле, что никакое другое подполе не содержит ни одного из них. Следовательно, они являются корнями неприводимых многочленов степени 6 над GF (2) . Отсюда следует, что над GF (2) ровно 9 =54/6неприводимые монические многочлены степени 6 . Это может быть проверено с помощью факторинга Х ⁶⁴ - Х над GF (2) .

Элементы GF (64) являются примитивными корнями n- й степени из единицы для некоторого n, делящего 63 . Поскольку 3-й и 7-й корни из единицы принадлежат GF (4) и GF (8) , соответственно, 54 образующих являются примитивными корнями n- й степени из единицы для некоторого n в {9, 21, 63} . Тотальная функция Эйлера показывает, что существует 6 примитивных корней 9- й степени из единицы, 12 примитивных корней 21- й степени из единицы и 36 примитивных корней 63- й степени из единицы. Суммируя эти числа, снова получается 54 элемента.

Факторизуя круговые полиномы над GF (2) , можно найти, что:

• Шесть примитивные 9 - й корнями из единицы являются корнями

${\ displaystyle X ^ {6} + X ^ {3} +1,}$

и все они сопряжены под действием группы Галуа.

• Двенадцать первобытных корней единства 21- го являются корнями

${\ displaystyle (X ^ {6} + X ^ {4} + X ^ {2} + X + 1) (X ^ {6} + X ^ {5} + X ^ {4} + X ^ {2} +1).}$

Они образуют две орбиты под действием группы Галуа. Поскольку два фактора взаимны друг другу, корень и его (мультипликативный) обратный не принадлежат одной и той же орбите.

• В 36 примитивные элементы GF (64) являются корнями

${\ displaystyle (X ^ {6} + X ^ {4} + X ^ {3} + X + 1) (X ^ {6} + X + 1) (X ^ {6} + X ^ {5} + 1) (X ^ {6} + X ^ {5} + X ^ {3} + X ^ {2} +1) (X ^ {6} + X ^ {5} + X ^ {2} + X + 1) (X ^ {6} + X ^ {5} + X ^ {4} + X + 1),}$

Под действием группы Галуа они разбиваются на 6 орбит из 6 элементов.

Это показывает, что лучший выбор для построения GF (64) - определить его как GF (2) [ X ] / ( X ⁶ + X + 1) . Фактически, этот генератор является примитивным элементом, а этот многочлен является неприводимым многочленом, который производит простейшее евклидово деление.

Автоморфизм Фробениуса и теория Галуа

В этом разделе p - простое число, а q = p ⁿ - степень p .

В GF ( q ) из тождества ( x + y ) ^p = x ^p + y ^p следует, что отображение

${\ displaystyle \ varphi: x \ mapsto x ^ {p}}$

является GF ( р ) - линейный эндоморфизм и полевой автоморфизм из GF ( д ) , который фиксирует каждый элемент подполя GF ( р ) . Он называется автоморфизмом Фробениуса в честь Фердинанда Георга Фробениуса .

Обозначая через ф ^К в композиции из ф с собой K раз, мы имеем

${\ displaystyle \ varphi ^ {k}: x \ mapsto x ^ {p ^ {k}}.}$

В предыдущем разделе было показано, что φ ⁿ является тождественным. При 0 < k < n автоморфизм φ ^k не является тождественным, как в противном случае многочлен

${\ displaystyle X ^ {p ^ {k}} - X}$

будет иметь более p ^k корней.

Других GF ( p ) -автоморфизмов GF ( q ) не существует . Другими словами, GF ( p ⁿ ) имеет ровно n GF ( p ) -автоморфизмов, которые являются

${\ displaystyle \ mathrm {Id} = \ varphi ^ {0}, \ varphi, \ varphi ^ {2}, \ ldots, \ varphi ^ {n-1}.}$

В терминах теории Галуа это означает, что GF ( p ⁿ ) является расширением Галуа группы GF ( p ) , которое имеет циклическую группу Галуа.

Из того факта, что отображение Фробениуса сюръективно, следует, что каждое конечное поле совершенно .

Полиномиальная факторизация

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

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

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

Неприводимые многочлены заданной степени

Полином

${\ displaystyle X ^ {q} -X}$

разлагается на линейные множители над полем порядка q . Точнее, этот многочлен является произведением всех монических многочленов первой степени над полем порядка q .

Отсюда следует, что если q = p ^n, то X ^q - X является произведением всех монических неприводимых многочленов над GF ( p ) , степень которых делит n . Фактически, если P - неприводимый фактор над GF ( p ) в X ^q - X , его степень делит n , так как его поле расщепления содержится в GF ( p ⁿ ) . Наоборот, если P - неприводимый монический многочлен над GF ( p ) степени d, делящий n , он определяет расширение поля степени d , которое содержится в GF ( p ⁿ ) , и все корни P принадлежат GF ( p ⁿ ) , и являются корнями X ^q - X ; Таким образом , Р делит Й ^д - Х . Поскольку X ^q - X не имеет кратных множителей, он, таким образом, является произведением всех неприводимых монических многочленов, которые его делят.

Это свойство используется для вычисления произведения неприводимых множителей каждой степени многочленов над GF ( p ) ; см. Факторизация отчетливой степени .

Число монических неприводимых многочленов заданной степени над конечным полем

Число N ( q , n ) монических неприводимых многочленов степени n над GF ( q ) задается формулой

${\ displaystyle N (q, n) = {\ frac {1} {n}} \ sum _ {d \ mid n} \ mu (d) q ^ {n / d},}$

где μ - функция Мёбиуса . Эта формула является почти прямым следствием выше свойства X ^ц - X .

По приведенной выше формуле количество неприводимых (не обязательно монических) многочленов степени n над GF ( q ) равно ( q - 1) N ( q , n ) .

Нижняя оценка (немного более простая) для N ( q , n ) равна

${\ displaystyle N (q, n) \ geq {\ frac {1} {n}} \ left (q ^ {n} - \ sum _ {p \ mid n, \ p {\ text {prime}}} q ^ {n / p} \ right).}$

Легко вывести, что для каждого q и любого n существует хотя бы один неприводимый многочлен степени n над GF ( q ) . Эта нижняя оценка точна при q = n = 2 .

Приложения

В криптографии сложность задачи дискретного логарифмирования в конечных полях или эллиптических кривых лежит в основе нескольких широко используемых протоколов, таких как протокол Диффи – Хеллмана . Например, в 2014 году безопасное интернет-соединение с Википедией задействовало протокол Диффи – Хеллмана с эллиптической кривой ( ECDHE ) над большим конечным полем. В теории кодирования , многие коды строятся как подпространства в векторных пространствах над конечными полями.

Конечные поля используются многими кодами исправления ошибок , такими как код исправления ошибок Рида – Соломона или код BCH . Конечное поле почти всегда имеет характеристику 2, поскольку компьютерные данные хранятся в двоичном формате. Например, байт данных можно интерпретировать как элемент . Единственным исключением является штрих-код PDF417 , то есть . Некоторые процессоры имеют специальные инструкции, которые могут быть полезны для конечных полей характеристики 2, как правило, вариаций продукта без переноса . ${\ displaystyle GF (2 ^ {8})}$${\ displaystyle GF (929)}$

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

Точно так же многие теоретические проблемы теории чисел могут быть решены путем рассмотрения их редукций по модулю некоторых или всех простых чисел. См., Например, принцип Хассе . Многие недавние разработки алгебраической геометрии были мотивированы необходимостью расширить возможности этих модульных методов. Доказательство Уайлса Великой теоремы Ферма является примером глубокого результата, включающего множество математических инструментов, включая конечные поля.

В догадках Weil касаются количества точек на алгебраических многообразиях над конечными полями и теория имеет множество приложений , включая экспоненциальные и характер суммы оценки.

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

Расширения

Алгебраическое замыкание

Конечное поле F не алгебраически замкнуто: многочлен

${\ Displaystyle F (T) = 1 + \ prod _ {\ alpha \ in F} (T- \ alpha),}$

не имеет корней в F , так как F  ( α ) = 1 для всех & alpha ; в F .

Фиксируем алгебраическое замыкание в . Отображение, переводящее каждый x в x ^q , называется автоморфизмом Фробениуса q- й степени . Подполе, зафиксированное n- й итерацией, представляет собой набор нулей многочлена x ^{q n} - x , который имеет различные корни, поскольку его производная в равна −1 , которая никогда не равна нулю. Следовательно, это подполе имеет q ⁿ элементов, поэтому оно является уникальной копией in . Каждое конечное расширение in является таковым для некоторого n , поэтому ${\ displaystyle {\ overline {\ mathbb {F}}} _ {q}}$${\ displaystyle \ mathbb {F} _ {q}}$${\ displaystyle \ varphi _ {q} \ двоеточие {\ overline {\ mathbb {F}}} _ {q} \ to {\ overline {\ mathbb {F}}} _ {q}}$${\ displaystyle {\ overline {\ mathbb {F}}} _ {q}}$${\ displaystyle \ varphi _ {q}}$${\ displaystyle \ mathbb {F} _ {q} [x]}$${\ Displaystyle \ mathbb {F} _ {д ^ {п}}}$${\ displaystyle {\ overline {\ mathbb {F}}} _ {q}}$${\ displaystyle \ mathbb {F} _ {q}}$${\ displaystyle {\ overline {\ mathbb {F}}} _ {q}}$${\ Displaystyle \ mathbb {F} _ {д ^ {п}}}$

${\ displaystyle {\ overline {\ mathbb {F}}} _ {q} = \ bigcup _ {n \ geq 1} \ mathbb {F} _ {q ^ {n}}.}$

Абсолютная группа Галуа из является проконечной группой${\ displaystyle \ mathbb {F} _ {q}}$

${\ displaystyle \ operatorname {Gal} ({\ overline {\ mathbb {F}}} _ {q} / \ mathbb {F} _ {q}) \ simeq \ varprojlim _ {n} \ operatorname {Gal} ({ \ overline {\ mathbb {F}}} _ {q ^ {n}} / \ mathbb {F} _ {q}) \ simeq \ varprojlim _ {n} (\ mathbf {Z} / n \ mathbf {Z} ) = {\ widehat {\ mathbf {Z}}}.}$

Подобно любой бесконечной группе Галуа, ее можно снабдить топологией Крулля , и тогда только что приведенные изоморфизмы будут изоморфизмами топологических групп . Изображение в группе - это генератор 1 , поэтому соответствует . Отсюда следует, что имеет бесконечный порядок и порождает плотную подгруппу , а не всю группу, потому что элемент имеет бесконечный порядок и порождает плотную подгруппу. Один говорит, что является топологическим генератором группы . ${\ displaystyle \ operatorname {Gal} ({\ overline {\ mathbb {F}}} _ {q} / \ mathbb {F} _ {q})}$${\ displaystyle \ varphi _ {q}}$${\ Displaystyle \ OperatorName {Gal} ({\ overline {\ mathbb {F}}} _ {q ^ {n}} / \ mathbb {F} _ {q}) \ simeq \ mathbf {Z} / n \ mathbf {Z}}$${\ displaystyle \ varphi _ {q}}$${\ displaystyle 1 \ in {\ widehat {\ mathbf {Z}}}}$${\ displaystyle \ varphi _ {q}}$${\ displaystyle \ operatorname {Gal} ({\ overline {\ mathbb {F}}} _ {q} / \ mathbb {F} _ {q})}$${\ displaystyle 1 \ in {\ widehat {\ mathbf {Z}}}}$${\ displaystyle \ mathbf {Z} \ subsetneqq {\ widehat {\ mathbf {Z}}}.}$${\ displaystyle \ varphi _ {q}}$${\ displaystyle \ operatorname {Gal} ({\ overline {\ mathbb {F}}} _ {q} / \ mathbb {F} _ {q})}$

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

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

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

Деление кольца является обобщением поля. Делительные кольца не считаются коммутативными. Не существует некоммутативных конечных тел: малая теорема Веддерберна утверждает, что все конечные тела коммутативны, следовательно, конечные поля. Результат верен, даже если мы ослабим ассоциативность и рассмотрим альтернативные кольца по теореме Артина – Цорна .

Смотрите также

• Квазиконечное поле
• Поле с одним элементом
• Конечнопольная арифметика
• Конечное кольцо
• Конечная группа
• Элементарная абелева группа
• Пространство Хэмминга

Примечания

использованная литература

внешние ссылки

• Конечные поля в исследовании Wolfram.