Polynomdivision im GF(2)

25.08.2004, 18:33

Andrew Wiles

Polynomdivision im GF(2)

Grüß' euch!

Bin gerade so bei der geistigen Aufarbeitung meines letzten Semesters.
Dabei fielen mir ein paar interessante Fragen bezüglich Polynomen
über dem Galoisfeld 2 (d.h. modulo 2) ein, die meine teils unfähigen Lehrkräfte auf der Uni und davor mir nicht oder nur unzureichend beantworten konnten.

1.) Wie dividiere ich grundsätzlich Polynome modulo 2
z.B. (x^4 + x + 1) : (x^2 + 1) = ?
Zugegebenermaßen konnte ich den Algorithmus (im Gegensatz zum allgemeinen) hier glaube ich schon,
aber ich habe ihn wieder vergessen geschockt

Und - wie unterscheidet sich der Divisionsvorgang bezüglich der herkömmlichen Polynomdivision?

2.) In GF(2) gilt ja meiner Meinung nach x = x^2 = x^3 usw = x^n
auch gilt x+x = 0 etc..
Sind dann nicht u.a. die Polynome x+1 und x^2+1 über diesem Feld die gleichen? Immerhin kann man einsetzen was man will und der "numerische Wert" der resultiert ist der gleiche. Somit könnte man bei der obigen Beispieldivision ja auch durch x+1 dividieren mit demselben Ergebnis, oder etwa nicht?

3.) Wenn ich ein irreduzibles Primitivpolynom gefunden habe, gilt das dann nur bezüglich dem entsprechenden Galoisfeld oder allgemein als irreduzibel?

Danke im Voraus für sinnvolle Beitrage - schätze habe in euch meine Gurus für die Zukunft gefunden.

25.08.2004, 18:51

Rinse

Auf diesen Beitrag antworten »

RE: Polynomdivision im GF(2)
Man muss Unterschied machen zwischen Polynome und Polynomfunctionen!

25.08.2004, 19:09

Andrew Wiles

Auf diesen Beitrag antworten »

RE: Polynomdivision im GF(2)
In der Tath - wo habe ich leicht Polynome mit Polynomfunctionen verwechselt? verwirrt

25.08.2004, 19:42

Oudeis

Auf diesen Beitrag antworten »

RE: Polynomdivision im GF(2)

Zitat:

Original von Andrew Wiles

1.) (...)
Und - wie unterscheidet sich der Divisionsvorgang bezüglich der herkömmlichen Polynomdivision?

Prinzipiell gar nicht, aber Dein Computer mag den Polynomring über $\begin{eqnarray*} F_2 \end{eqnarray*}$ besonders gerne, weil er da besonders wenig tun muss (Polynome $\begin{eqnarray*} f,g \in F_2[X] \end{eqnarray*}$ lassen sich als Bitvektoren darstellen, und dann ist f + g = f xor g, f*X^n = f um n Stellen nach links geschoben usw.).

Zitat:

2.) In GF(2) gilt ja meiner Meinung nach x = x^2 = x^3

Natürlich gilt im Körper mit zwei Elementen für alle x, daß $\begin{eqnarray*} x^2 = x \end{eqnarray*}$ . Im Polynomring über diesem Körper gilt nichts entsprechendes (beachte die relevanten Definitionen in Deiner Vorlesung).

Zitat:

Immerhin kann man einsetzen was man will und der "numerische Wert" der resultiert ist der gleiche.

Ja, die Intuition, daß Polynome mit gleichem Wertverlauf der Polynomfunktion gleich wären, stimmt nur für unendliche Körper.

Zitat:

3.) Wenn ich ein irreduzibles Primitivpolynom gefunden habe, gilt das dann nur bezüglich dem entsprechenden Galoisfeld oder allgemein als irreduzibel?

Ich verstehe die Frage nicht. Wenn Du über irgendeinem Körper ein irreduzibles Polynom findest, dann kommt dieses Polynom nicht vor in den Polynomringen anderer Körper (natürlich kann es sein, daß Du die Irreduzibilität eines Polynoms woanders auf einen passenden Fall beispielsweise in einem endlichen Körper zurückführen kannst, aber dazu brauchst Du Argumente, entweder vorgefertigt aus einem passenden Satz oder selber erdacht). Ein in einem Körper irreduzibles Polynom ist i.A. nicht irreduzibel in einer Körpererweiterung, betrachte etwa den Fall $\begin{eqnarray*} X^2+1 \in \mathbb{R}[X] \end{eqnarray*}$ versus das gleiche über $\begin{eqnarray*} \mathbb{C} \end{eqnarray*}$ (oder, wenn Du lieber endliche Beispiele magst, auch $\begin{eqnarray*} X^2 + X + 1 \in F_2[X] \end{eqnarray*}$ versus das gleiche über $\begin{eqnarray*} F_2[X]/(X^2 + X + 1) \end{eqnarray*}$ ).

Grüße,
Oudeis.

26.08.2004, 02:14

Rinse

Auf diesen Beitrag antworten »

RE: Polynomdivision im GF(2)
Bei "x = x^2 = x^3 usw = x^n" z.B.

26.08.2004, 13:11

Andrew Wiles

Auf diesen Beitrag antworten »

RE: Polynomdivision im GF(2)
Wir sollten damals herausfinden ob ein gewisses Polynom über GF(2)
irreduzibel ist und es zu diesem Zwecke durch alle "kleineren" Polynome
dividieren.
Um noch zu unterstreichen um was es mir eigentlich ging
Ein Beispiel:

(x^4+x+1) : (x^2 + 1) = x^2 + 1
x^4 + x^2
----------------
x^2+x+1
X^2+1
----------------
x Rest

Angenommen ich habe oben jetzt richtig dividiert (glaube schon!?)
hätte man dann nicht ohne dividieren gleich erkennen können
wegen x^4 + x + 1 = 1
und x^2 + 1 = 0 oder 1
dass eine Division ohne Rest nicht möglich ist?

Zitat:

beachte die relevanten Definitionen in Deiner Vorlesung

Das Problem ist ja, dass ich kein Mathematiker bin und mir scheinbar hier ein paar Grundlagen fehlen.
Der Vorlesende nahm an der Hintergrund wäre vorhanden, was bei mir und denen meines Jahrgangs nicht zutraf.

26.08.2004, 14:05

Irrlicht

Auf diesen Beitrag antworten »

Hallo Mr. Wiles, (das ist ja ein Gefühl sowas zu sagen *g*)

Deine Polynomdivision ist richtig ausgeführt.

Das von dir vorgebrachte Argument ist ebenfalls richtig. Man kann hier durch Betrachtung der Nullstellen entscheiden, dass die Polynomdivision nicht ohne Rest durchführbar ist:

x^4 + x + 1 hat in GF_2 keine Nullstellen, aber x^2 + 1 hat eine Nullstelle. Damit kann x^2 + 1 kein Teiler von x^4 + x + 1 im Polynomring GF_2[x] sein. Dasselbe Argument würde funktionieren, wenn der Divisor (= der Nenner eines Bruches) eine Nullstelle hat, die der Dividend (= Zähler eines Bruches) nicht hat.

Die Tatsache, dass Vorlesende stillschweigend diverse Vorkenntnisse voraussetzen, ist nicht böser Wille des Vorlesenden. Er muss ja schliesslich irgendwo anfangen. Leider wird bei der Wahl dieser Grundkenntnisse immer jemand dabei sein, der diese nicht hat.
Wenn allerdings der gesamte Kurs keine Ahnung hat, dann sollte man das dem Dozenten sagen. Wenn er dann noch schweigt, dann... naja... kann man sich seine Meinung über den Dozenten ja bilden. Augenzwinkern

Liebe Grüsse,
Irrlicht

Neue Frage »

Antworten »

Polynomdivision im GF(2)

Verwandte Themen