GF (2) - GF(2)
GF (2) (также обозначается , Z / 2 Z или ) представляет собой конечное поле из двух элементов (GF является аббревиатурой из поля Галуа , другое название для конечных полей). Обозначения Z 2 и могут встречаться, хотя их можно спутать с обозначениями2 -адические целые числа .
GF (2) - это поле с наименьшим возможным числом элементов, и оно уникально, если аддитивная единица и мультипликативная единица обозначены соответственно0 и1 , как обычно.
Элементы GF (2) могут быть идентифицированы двумя возможными значениями бита и логическими значениями истина и ложь . Отсюда следует, что 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 должно быть степенью 2 (или бесконечным числом ).
В современных компьютерах данные представлены битовыми строками фиксированной длины, называемыми машинными словами . Они наделены структурой векторного пространства над GF (2). Добавление этого векторного пространства - это побитовая операция, называемая XOR (исключающее ИЛИ ). Побитовое И еще одна операция на этом векторном пространстве, что делает его Булева алгебра , структура , которая лежит в основе всех информатику . Эти пространства также могут быть дополнены операцией умножения, которая превращает их в поле GF (2 n ), но операция умножения не может быть побитовой. Когда n само является степенью двойки, операция умножения может быть nim-умножением ; в качестве альтернативы, для любого n можно использовать умножение многочленов над GF (2) по модулю неприводимого многочлена (как, например, для поля GF (2 8 ) в описании шифра Advanced Encryption Standard ).
Векторные пространства и кольца многочленов над GF (2) широко используются в теории кодирования и, в частности, в кодах с исправлением ошибок и современной криптографии . Например, многие распространенные коды с исправлением ошибок (такие как коды BCH ) являются линейными кодами над GF (2) (коды, определенные из векторных пространств над GF (2)) или полиномиальными кодами (коды, определенные как частные полиномиальных колец над GF (2 )).
Смотрите также
использованная литература
- Лидл, Рудольф; Нидеррайтер, Харальд (1997). Конечные поля . Энциклопедия математики и ее приложений. 20 (2-е изд.). Издательство Кембриджского университета . ISBN 0-521-39231-4. Zbl 0866.11069 .