Gauss Elimination im endlichen Körper

23.05.2013, 13:06

Blubba69

Gauss Elimination im endlichen Körper

Hallo!

Ich muss für ein Beispiel die Gauss Elimination auf einen endlichen Körper anwenden. Genauer gesagt handelt es sich dabei um einen Körper mit 256 Elementen (GF(2^8)) der mit folgendem Polynom erzeugt wird:

$\begin{eqnarray*} P(x) = x^8 + x^4 + x^3 + x^2 + 1 \end{eqnarray*}$

Die Gleichungen lauten folgendermaßen:

$\begin{eqnarray*} \begin{pmatrix} 1 & 1 & 1 & 1 & 0 \\ 8 & 4 & 2 & 1 & 106 \\ 27 & 9 & 3 & 1 & 165 \\ 64 & 16 & 4 & 1 & 187 \\ 125 & 25 & 5 & 1 & 83 \end{pmatrix} \end{eqnarray*}$

Mit dem Lösungsvektor:

$\begin{eqnarray*} \begin{pmatrix} 0 \\ 212 \\ 242 \\ 214 \\ 2 \end{pmatrix} \end{eqnarray*}$

Ich hab nun einfach das Gaussverfahren darauf angewendet und dabie ist folgendes bei mir rausgekommen:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:

----------
1	1	1	1	0	0	
8	4	2	1	106	212	
27	9	3	1	165	242	
64	16	4	1	187	214	
125	25	5	1	83	2	
----------
----------
1	1	1	1	0	0	
0	12	10	9	106	212	
0	18	24	26	165	242	
0	80	68	65	187	214	
0	100	120	124	83	2	
----------
----------
1	1	1	1	0	0	
0	1	143	200	135	19	
0	0	3	139	46	249	
0	0	60	45	121	79	
0	0	46	51	2	160	
----------
----------
1	1	1	1	0	0	
0	1	143	200	135	19	
0	0	1	121	26	87	
0	0	0	99	27	167	
0	0	0	76	233	255	
----------
----------
1	1	1	1	0	0	
0	1	143	200	135	19	
0	0	1	121	26	87	
0	0	0	1	214	181	
0	0	0	0	203	150	
----------
----------
1	1	1	1	0	0	
0	1	143	200	135	19	
0	0	1	121	26	87	
0	0	0	1	214	181	
0	0	0	0	1	14	
----------

Das ergibt die Lösungen: 133 13 192 72 14

Wenn ich jetzt aber versuche z.B. in die zweite Gleichung diese Lösungen einzusetzen:

$\begin{eqnarray*} \Rightarrow 8*133 + 13*4 + 2*192 + 1*72 + 106 \neq 212 \end{eqnarray*}$

Dann kommt nicht das richtige dabei raus. Könnt ihr mir vielleicht ein wenig helfen und sagen wo der Fehler liegt. Soweit ich weiß sollte nämlich die Gaussche Elimination für endliche Körper funktionieren.

Danke schonmal im Voraus!
Lg

23.05.2013, 16:42

watcher

Auf diesen Beitrag antworten »

Hallo Blubba69,

ja der Gauß-Algorithmus funktioniert "auch" in endlichen Körpern.

Leider kann ich deine Rechnungen nicht wirklich nachvollziehen.
Ihr scheint GF(256) mit {0,..., 255} zu identifizieren.
Wie macht ihr das genau? mit der Ersetzeung $\begin{eqnarray*} X \mapsto 2 \end{eqnarray*}$ ?

23.05.2013, 18:19

Blubba69

Auf diesen Beitrag antworten »

Zitat:

Original von watcher
Hallo Blubba69,

ja der Gauß-Algorithmus funktioniert "auch" in endlichen Körpern.

Leider kann ich deine Rechnungen nicht wirklich nachvollziehen.
Ihr scheint GF(256) mit {0,..., 255} zu identifizieren.
Wie macht ihr das genau? mit der Ersetzeung $\begin{eqnarray*} X \mapsto 2 \end{eqnarray*}$ ?

Erstmal danke für deine Antwort.

Ja genau interpretiert wird das eben als ein Feld mit 256 Elementen. Der Grund dafür ist, da das in einem Programm so implementiert wird und dort mit Bytes gearbeitet wird (die eben genau Werte von 0 bis 255 annehmen können).

Vielleicht noch kurz ergänzend: Die Addition ist mit a+b = a XOR b umgesetzt, die Multiplikation und Division über eine Logarithmustabelle (siehe z.B.: logic.at/wiki/index.php/GF(256))

Die Gleichungen die verwendet werden haben eine spezielle Form:

$\begin{eqnarray*} ax^3 + bx^2 + cx + d +e*z = x * z \end{eqnarray*}$

Wobei x die Variable ist und z einem Element aus dem Lösungsvektor entspricht. z.B. folgender Punkt P(2/212) entspricht der Gleichung:

$\begin{eqnarray*} 8a + 4b + 2c + d + 212e = 2*212 \end{eqnarray*}$

Daraus entstehen die Gleichungen.

Lg

23.05.2013, 19:08

watcher

Auf diesen Beitrag antworten »

Zitat:

as ergibt die Lösungen: 133 13 192 72 14 Wenn ich jetzt aber versuche z.B. in die zweite Gleichung diese Lösungen einzusetzen: $\begin{eqnarray*} \Rightarrow 8*133 + 13*4 + 2*192 + 1*72 + 106 \neq 212 \end{eqnarray*}$

Es müsste heißen:
$\begin{eqnarray*} \Rightarrow 8*133 + 13*4 + 2*192 + 1*72 + \color{red}14 \cdot \color{black}106 \end{eqnarray*}$

Die Umformungen im ersten Schritt sind wohl richtig. Den Rest müsste ich auch programmieren, per Hand schaff ich das nicht so schnell.

23.05.2013, 20:27

blubba69

Auf diesen Beitrag antworten »

Zitat:

Original von watcher

Zitat:

Okay das hab ich wohl vergessen hin zu schreiben. Wenn ich das allerdings ausrechne, dann kommt eben als Ergebnis: 171 raus und nicht 212.

Lg

23.05.2013, 22:03

watcher

Auf diesen Beitrag antworten »

So, habs mal mein CAS rechnen lassen und krieg (23,253,165,79,82)
raus.
Bin nicht direkt über Gauß gegegangen sondern hab die Matrix invertiert.

Neue Frage »

Antworten »

Gauss Elimination im endlichen Körper

Verwandte Themen