GF(2) - GF(2)

GF(2) (auch bezeichnet als , Z /2 Z oder ) ist der endliche Körper von zwei Elementen (GF ist der Initialismus von Galois-Feld , ein anderer Name für endliche Körper ). Notationen Z ₂ und können angetroffen werden, obwohl sie mit der Notation von verwechselt werden können${\displaystyle \mathbb{F}_{2}}$${\displaystyle \mathbb{Z}/2\mathbb{Z}}$${\displaystyle \mathbb {Z} _{2}}$2 -adische ganze Zahlen .

GF(2) ist das Feld mit der kleinstmöglichen Anzahl von Elementen und ist eindeutig, wenn die additive Identität bzw. die multiplikative Identität bezeichnet wird0 und1 , wie gewohnt.

Die Elemente von GF(2) können mit den zwei möglichen Werten eines Bits und den booleschen Werten true und false identifiziert werden . Daraus folgt, dass GF(2) in der Informatik und ihren logischen Grundlagen grundlegend und allgegenwärtig ist .

Definition

GF(2) ist das eindeutige Feld mit zwei Elementen mit seinen additiven bzw. multiplikativen Identitäten bezeichnet0 und1 .

Seine Addition ist definiert als die übliche Addition von ganzen Zahlen aber modulo 2 und entspricht der folgenden Tabelle:

+	0	1
0	0	1
1	1	0

Wenn die Elemente von GF(2) als boolesche Werte angesehen werden, dann ist die Addition dieselbe wie bei der logischen XOR- Operation. Da jedes Element gleich seinem Gegenteil ist , ist die Subtraktion also die gleiche Operation wie die Addition.

Die Multiplikation von GF(2) ist wieder die übliche Multiplikation modulo 2 (siehe Tabelle unten) und entspricht bei booleschen Variablen der logischen UND- Verknüpfung.

×	0	1
0	0	0
1	0	1

GF(2) kann identifiziert werden mit dem Körper der ganzen Zahlen modulo2 , also der Quotientenring des Rings der ganzen Zahlen Z durch das ideale 2 Z aller geraden Zahlen : GF(2) = Z /2 Z .

Eigenschaften

Da GF(2) ein Körper ist, bleiben viele der bekannten Eigenschaften von Zahlensystemen wie den rationalen Zahlen und reellen Zahlen erhalten:

• Addition hat ein Identitätselement (0) und eine Umkehrung für jedes Element;
• Multiplikation hat ein Identitätselement (1) und eine Umkehrung für jedes Element außer 0;
• Addition und Multiplikation sind kommutativ und assoziativ ;
• Multiplikation ist distributiv über Addition.

Zu den Eigenschaften, die von den reellen Zahlen nicht bekannt sind, gehören:

• jedes Element x von GF(2) erfüllt x + x = 0 und daher − x = x ; dies bedeutet, dass die Charakteristik von GF(2) 2 ist;
• jedes Element x von GF(2) erfüllt x ² = x (dh ist bezüglich der Multiplikation idempotent ); Dies ist ein Beispiel für den kleinen Satz von Fermat . GF(2) ist der einzige Körper mit dieser Eigenschaft (Beweis: wenn x ² = x , dann entweder x = 0 oder x ≠ 0 . Im letzteren Fall muss x eine multiplikative Inverse haben, in diesem Fall dividieren beide Seiten durch x ergibt x = 1. Alle größeren Felder enthalten andere Elemente als 0 und 1, und diese Elemente können diese Eigenschaft nicht erfüllen).

Anwendungen

Aufgrund der oben genannten algebraischen Eigenschaften funktionieren viele bekannte und mächtige Werkzeuge der Mathematik in GF(2) genauso gut wie in anderen Gebieten. Zum Beispiel können Matrixoperationen, einschließlich Matrixinversion , auf Matrizen mit Elementen in GF(2) angewendet werden ( siehe Matrixring ).

Jede Gruppe V mit der Eigenschaft v  +  v  = 0 für jedes v in V (dh jedes Element ist eine Involution ) ist notwendigerweise abelsch und kann auf natürliche Weise in einen Vektorraum über GF(2) umgewandelt werden, indem man 0 v  = . definiert 0 und 1 v  =  v . Dieser Vektorraum hat eine Basis , was bedeutet, dass die Anzahl der Elemente von V eine Potenz von 2 (oder unendlich) sein muss.

In modernen Computern werden Daten mit Bitfolgen fester Länge, sogenannten Maschinenwörtern, dargestellt . Diese sind mit der Struktur eines Vektorraums über GF(2) ausgestattet. Die Addition dieses Vektorraums ist die bitweise Operation namens XOR (exklusives Oder). Das bitweise UND ist eine weitere Operation in diesem Vektorraum, was ihn zu einer Booleschen Algebra macht , einer Struktur, die der gesamten Informatik zugrunde liegt . Diese Räume können auch durch eine Multiplikationsoperation erweitert werden, die sie zu einem Feld GF(2 ⁿ ) macht, aber die Multiplikationsoperation kann keine bitweise Operation sein. Wenn n selbst eine Zweierpotenz ist, kann die Multiplikationsoperation eine nim-Multiplikation sein ; alternativ kann man für jedes n die Multiplikation von Polynomen über GF(2) modulo ein irreduzibles Polynom verwenden (wie zum Beispiel für das Feld GF( ²⁸ ) in der Beschreibung der Advanced Encryption Standard- Chiffre).

Vektorräume und Polynomringe über GF(2) werden häufig in der Codierungstheorie und insbesondere in Fehlerkorrekturcodes und moderner Kryptographie verwendet . Zum Beispiel sind viele übliche Fehlerkorrekturcodes (wie BCH-Codes ) lineare Codes über GF(2) (Codes, die aus Vektorräumen über GF(2) definiert sind) oder polynomiale Codes (Codes, die als Quotienten von Polynomringen über GF(2 )).

Siehe auch

• Feld mit einem Element

Verweise

• Lidl, Rudolf; Niederreiter, Harald (1997). Endliche Felder . Enzyklopädie der Mathematik und ihrer Anwendungen. 20 (2. Aufl.). Cambridge University Press . ISBN 0-521-39231-4. Zbl  0866.11069 .