ГФ(2)
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, и соответствует таблице ниже:
| + | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
Если элементы GF(2) рассматриваются как логические значения, то сложение происходит так же, как и при логической операции XOR .Поскольку каждый элемент равен противоположному , вычитание — это та же операция, что и сложение.
Умножение GF(2) снова представляет собой обычное умножение по модулю 2 (см. таблицу ниже), а для логических переменных соответствует И. логической операции
| × | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
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 2 = x (т.е. идемпотент относительно умножения); это пример маленькой теоремы Ферма . GF(2) — единственное поле с этим свойством (Доказательство: если x 2 = 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 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 н ); копия GF(2 н ) содержится в копии GF(2 м ) тогда и только тогда, когда n делит m. Поле F счетно и представляет собой объединение всех этих конечных полей.
Конвей понял, что F можно отождествить с порядковым номером , где операции сложения и умножения определяются естественным образом с помощью трансфинитной индукции (однако эти операции отличаются от стандартного сложения и умножения порядковых чисел). [2] Сложение в этом поле выполняется просто и похоже на сложение Нима ; Ленстра показал, что умножение также можно выполнять эффективно. [3]
См. также [ править ]
Ссылки [ править ]
- ^ Лидл, Рудольф; Нидеррайтер, Харальд (1997). Конечные поля . Энциклопедия математики и ее приложений. Том. 20 (2-е изд.). Издательство Кембриджского университета . ISBN 0-521-39231-4 . Збл 0866.11069 .
- ^ Конвей, Джон Х. (2000). О числах и играх (2-е изд.). Уэлсли, Массачусетс, с. 61. ИСБН 978-1-56881-127-7 .
{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) - ^ Ленстра, Хендрик (1977). «Об алгебраическом замыкании двух» (PDF) . Indagationes Mathematicae (Труды) . 80 (5).