ГФ(2)

$GF(2)$ (также обозначается , $Z$ $/2$ $Z$ или ) — конечное поле с двумя элементами. ^[1]^[a] $\mathbb {F} _{2}$ $\mathbb {Z} /2\mathbb {Z}$

$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 .

Обозначения $Z 2$ и могут встречаться, хотя их можно спутать с обозначениями $\mathbb {Z} _{2}$ 2- адические целые числа .

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

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

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

Свойства, которые не знакомы из реальных чисел, включают в себя:

каждый элемент x из GF(2) удовлетворяет условию $x + x = 0$ и, следовательно, $- x = x$ ; это означает, что характеристика GF(2) равна 2;
каждый элемент x из GF(2) удовлетворяет условию $x 2 = x$ (т. е. является идемпотентом относительно умножения); это пример малой теоремы Ферма . GF(2) — единственное поле с этим свойством (Доказательство: если $x 2 = x$ , то либо $x = 0$ , либо $x \neq 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 само является степенью двойки, операция умножения может быть ним-умножением ; в качестве альтернативы, для любого 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] $\omega ^{\omega ^{\omega }}$

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

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

Ссылки

^ GF — это аббревиатура поля Галуа , другого названия конечных полей.

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