Эта статья требует дополнительных ссылок для проверки . ( август 2012 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
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 можно использовать умножение многочленов над 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 .