ГФ(2)

Конечное поле двух элементов

GF(2) ( также обозначаемый Z /2 Z или ) — это конечное поле с двумя элементами ^[1] (GF — это инициализм поля Галуа , другое название конечных полей). Обозначения Z ₂ и встречаются, хотя их можно спутать с обозначениями ${\displaystyle \mathbb {F} _{2}}$ ${\displaystyle \mathbb {Z} /2\mathbb {Z} }$ ${\displaystyle \mathbb {Z} _{2}}$2 -адические целые числа .

GF(2) — это поле с наименьшим возможным числом элементов, и оно уникально, если обозначены аддитивная и мультипликативная тождества соответственно.0 и1 , как обычно.

Элементы GF(2) могут быть идентифицированы двумя возможными значениями бита и логическими значениями true и false . Отсюда следует, что GF(2) является фундаментальным и повсеместным в информатике и ее логических основах.

Определение

GF(2) — уникальное поле из двух элементов, аддитивные и мультипликативные тождества которого обозначаются соответственно0 и1 .

Его сложение определяется как обычное сложение целых чисел, но по модулю 2, и соответствует таблице ниже:

Если элементы GF(2) рассматриваются как логические значения, то сложение происходит так же, как и при логической операции XOR . Поскольку каждый элемент равен противоположному , вычитание — это та же операция, что и сложение.

Умножение GF(2) снова представляет собой обычное умножение по модулю 2 (см. таблицу ниже), а для логических переменных соответствует логической операции И.

GF(2) можно отождествить с полем целых чисел по модулю2 , то есть факторкольцо кольца целых Z по идеалу 2 Z всех четных чисел : GF(2) = Z /2 Z .

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

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

• Сложение имеет единичный элемент (0) и обратный для каждого элемента;
• умножение имеет единичный элемент (1) и обратный для каждого элемента, кроме 0;
• Сложение и умножение коммутативны и ассоциативны ;
• умножение распределительно по сравнению с сложением.

К свойствам, незнакомым из действительных чисел, относятся:

• каждый элемент x из GF(2) удовлетворяет условию x + x = 0 и, следовательно, − x = x ; это означает, что характеристика GF(2) равна 2;
• каждый элемент x группы GF(2) удовлетворяет условию x ² = x (т.е. является идемпотентным относительно умножения); это пример маленькой теоремы Ферма . GF(2) — единственное поле с этим свойством (Доказательство: если x ² = x , то либо x = 0 , либо x ≠ 0. В последнем случае x должен иметь мультипликативную обратную величину, и в этом случае обе части делятся на x . дает x = 1. Все поля большего размера содержат элементы, отличные от 0 и 1, и эти элементы не могут удовлетворять этому свойству).

Приложения

Благодаря указанным выше алгебраическим свойствам многие знакомые и мощные математические инструменты работают в GF(2) так же, как и в других областях. Например, матричные операции, включая инверсию матрицы , можно применять к матрицам с элементами из GF(2) ( см. кольцо матриц ).

Любая группа ( V,+ ) со свойством v  +  v  = 0 для каждого v в V обязательно абелева и может быть естественным образом превращена в векторное пространство над GF(2), определив 0 v  = 0 и 1 v  =  v для всех v в V . Это векторное пространство будет иметь базис , а это означает, что количество элементов V должно быть степенью 2 (или бесконечностью).

В современных компьютерах данные представлены битовыми строками фиксированной длины, называемыми машинными словами . Они наделены структурой векторного пространства над GF(2). Добавление этого векторного пространства представляет собой побитовую операцию , называемую XOR (исключающее или). Побитовое И — это еще одна операция над этим векторным пространством, которая делает его булевой алгеброй — структурой, лежащей в основе всей информатики . Эти пространства также можно дополнить операцией умножения, которая превратит их в поле GF(2 ⁿ ), но операция умножения не может быть побитовой операцией. Когда n само является степенью двойки, операция умножения может быть nim-multiplication ; альтернативно, для любого n можно использовать умножение полиномов на GF(2) по модулю неприводимого многочлена (как, например, для поля GF(2 ⁸ ) в описании шифра Advanced Encryption Standard ).

Векторные пространства и кольца полиномов над GF(2) широко используются в теории кодирования , в частности в кодах с исправлением ошибок и современной криптографии . Например, многие распространенные коды с исправлением ошибок (такие как коды BCH ) представляют собой линейные коды над GF(2) (коды, определенные из векторных пространств над GF(2)) или полиномиальные коды (коды, определенные как частные колец многочленов над GF(2) )).

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

Как и любое поле, GF(2) имеет алгебраическое замыкание . Это поле F , которое содержит GF(2) в качестве подполя , которое является алгебраическим над GF(2) (т.е. каждый элемент F является корнем многочлена с коэффициентами из GF(2)), и которое алгебраически замкнуто ( любой непостоянный многочлен с коэффициентами из F имеет корень из F ). Этими свойствами поле F определяется однозначно с точностью до автоморфизма поля ( т.е., по существу, с точностью до обозначений его элементов).

F счетно и содержит по одной копии каждого из конечных полей GF(2 ⁿ ); копия GF(2 ⁿ ) содержится в копии GF(2 ^m ) тогда и только тогда, когда n делит m. Поле F счетно и представляет собой объединение всех этих конечных полей.

Конвей понял, что F можно отождествить с порядковым числом , где операции сложения и умножения определяются естественным образом с помощью трансфинитной индукции (однако эти операции отличаются от стандартного сложения и умножения порядковых чисел). ^[2] Сложение в этом поле простое в исполнении и похоже на сложение Нима ; Ленстра показал, что умножение также можно выполнять эффективно. ^[3] ${\displaystyle \omega ^{\omega ^{\omega }}}$

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

• Поле с одним элементом

Рекомендации

1. Лидл, Рудольф; Нидеррайтер, Харальд (1997). Конечные поля . Энциклопедия математики и ее приложений. Том. 20 (2-е изд.). Издательство Кембриджского университета . ISBN 0-521-39231-4. Збл  0866.11069.
2. Конвей, Джон Х. (2000). О числах и играх (2-е изд.). Уэлсли, Массачусетс, с. 61. ИСБН 978-1-56881-127-7.{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
3. Ленстра, Хендрик (1977). «Об алгебраическом замыкании двух» (PDF) . Indagationes Mathematicae (Труды) . 80 (5).