GF(2) ( также обозначаемый Z /2 Z или ) — это конечное поле с двумя элементами [1] (GF — это инициализм поля Галуа , другое название конечных полей). Обозначения 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) является полем, сохраняются многие знакомые свойства систем счисления, такие как рациональные и действительные числа :
К свойствам, незнакомым из действительных чисел, относятся:
Благодаря указанным выше алгебраическим свойствам многие знакомые и мощные математические инструменты работают в 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 само является степенью двойки, операция умножения может быть nim-multiplication ; альтернативно, для любого n можно использовать умножение полиномов на GF(2) по модулю неприводимого многочлена (как, например, для поля GF(2 8 ) в описании шифра 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 n ); копия GF(2 n ) содержится в копии GF(2 m ) тогда и только тогда, когда n делит m. Поле F счетно и представляет собой объединение всех этих конечных полей.
Конвей понял, что F можно отождествить с порядковым числом , где операции сложения и умножения определяются естественным образом с помощью трансфинитной индукции (однако эти операции отличаются от стандартного сложения и умножения порядковых чисел). [2] Сложение в этом поле простое в исполнении и похоже на сложение Нима ; Ленстра показал, что умножение также можно выполнять эффективно. [3]
{{cite book}}
: CS1 maint: отсутствует местоположение издателя ( ссылка )