Polynomring - Was ist das? < Klassen 8-10 < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:46 So 28.09.2008 | | Autor: | kawu |
Hallo!
Seit einigen Tagen befasse ich mich nun mit endlichen Körpern und um es gleich zu sagen: ich beschäftige mich damit aus persönlichem Interesse und nicht, weil ich in der Schule oder sonst wo verlangt wird, dass ich das verstehe (das scheint hier von großer Bedeutung zu sein, da man sonst an den Mathelehrer verwiesen wird *g*)
Um zum Problem zu kommen: Ich verstehe weder, was ein Polynomring bewikt, noch was man mit ihm macht. Schon den ganzen Tag befasse ich mich damit und habe fleißig gesucht, stolpere aber nur über kryptische Formeln, die den Anschein erwecken, dass sie eher für die Leser gedacht sind, die schon wissen, was Polynomringe sind.
Könnte mir hier jemand, auch wenn das mehr als unüblich ist, an einem Beispiel erklären, was Polynomringe sind?
Danke schonmal an alle, die mir behilflich sein können und wollen!
Kawu
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:57 So 28.09.2008 | | Autor: | vivo |
Hallo,
ein Polynomring ist die Menge aller Polynome mit Koeffizienten aus einem Ring.
Ein Polynom ist folgendermaßen definiert:
P(x) = [mm] \summe_{i=0}^{n}a_ix^i
[/mm]
die [mm] a_i [/mm] stammen dabei aus einem Ring zum beispiel den reellen Zahlen.
hoffe das hilft
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 07:57 Mo 29.09.2008 | | Autor: | kawu |
Nun, das ist ziemlich allgemein, wo ich doch nach einem Beispiel gefragt habe, mit dem sich diese allgemeinen Formeln besser begreifen lassen. Eine Additionsrechnung (das ist doch ein Summenzeichen) dieser Art sehe ich zum ersten Mal und dementsprechend viel kann ich auch damit in dem Zusammenhang anfangen.
[mm]\mathds{K} = \mathds{Z}_{5}[/mm]
Nehmen wir mal an, hier gibt es wirklich jemanden, der bereit ist, mir das anhand eines BEISPIELS begreiflich zu machen, könnte sich an Körper[mm]\mathds{K}[/mm] ein Polynomemring erstellen lassen?
lg, kawu
|
|
|
| |
|
> Nun, das ist ziemlich allgemein, wo ich doch nach einem
> Beispiel gefragt habe,
Hallo,
ein Beispiel, nämlich die Polynome über [mm] \IR, [/mm] hat vivo geliefert - daß Du Dir die Antwort irgendwie anders vorgestellt hast, steht auf einem anderen Blatt.
> [mm]\mathds{K} = \mathds{Z}_{5}[/mm]
>
> Nehmen wir mal an, hier gibt es wirklich jemanden, der
> bereit ist, mir das anhand eines BEISPIELS begreiflich zu
> machen, könnte sich an Körper[mm]\mathds{K}[/mm] ein Polynomemring
> erstellen lassen?
Ja, das geht.
Ich gehe davon aus, daß Du darüber informiert bist, welche Eigenschaften ein Ring hat.
Man kann nun zeigen, daß die Polynome über [mm] \mathds{Z}_{5}, [/mm] die Polynome mit Koeffizienten aus [mm] \IZ_5, [/mm] einen Ring bilden - dafür müssen wir uns gleich noch Gedanken machen, wie wir Polynome verknüpfen.
Erstmal zu den Polynomen über [mm] \mathds{Z}_{5}:
[/mm]
[mm] \mathds{Z}_{5} [/mm] kennst Du. Ich schreibe der Deutlichkeit halber Elemente aus [mm] \IZ_5 [/mm] mit Querstrich, damit wir sie von ganzen Zahlen unterscheiden.
Ein Polynom über [mm] \IZ_5 [/mm] wäre z.B. [mm] p_1=\overline{2}x^3+\overline{3}x^2 +\overline{4}.
[/mm]
Allgemein lassen sich Polynome über [mm] \ZI_5 [/mm] schreiben als [mm] p=a_nx^n+a_{n-1}x^{n-1}+ [/mm] ... + [mm] a_2x^2 [/mm] + a_1x+ [mm] a_0x^0 [/mm] mit Koeffizienten [mm] a_n, a_{n-1}, [/mm] ..., [mm] a_2,a_1, a_0 [/mm] aus [mm] \IZ_5.
[/mm]
Man kann sich nun Verknüpfungen überlegen, mit denen man jeweils zwei Polynome verknüpft .
Mit den Verknüpfungen, die ich gleich vorstellen werde, bildet die Menge der Polynome über [mm] \IZ [/mm] _5 eine Ring.
1. Die Addition zweier Polynome [mm] \oplus:
[/mm]
Es seien
[mm] p=a_nx^n+a_{n-1}x^{n-1}+ [/mm] ... + [mm] a_2x^2 [/mm] + a_1x+ [mm] a_0x^0 [/mm] mit Koeffizienten [mm] a_n, a_{n-1}, [/mm] ..., [mm] a_2,a_1, a_0 [/mm] aus [mm] \IZ_5
[/mm]
[mm] q=b_mx^m+b_{m-1}x^{m-1}+ [/mm] ... + [mm] b_2x^2 [/mm] + b_1x+ [mm] b_0x^0 [/mm] mit Koeffizienten [mm] b_m, a_{m-1}, [/mm] ..., [mm] b_2,b_1, b_0 [/mm] aus [mm] \IZ_5
[/mm]
zwei Polynome.
[mm] p\oplus [/mm] q definiert man nun so:
[mm] p\oplus [/mm] q:= [mm] \sum_{k=0}^{\max(m,n)}(a_k+b_k) x^k, [/mm] die Koeffizienten, die im "kleineren" der Polynome nicht mehr vorkommen setzt man hierfür =0.
Ich mach Dir das mal an einem Beispiel vor:
[mm] p_1=\overline{2}x^3+\overline{3}x^2 +\overline{4}x^0
[/mm]
[mm] p_2=\overline{4}x^2 +\overline{2}x [/mm] + [mm] \overline{1}x^0
[/mm]
Es ist [mm] p_1\oplus p_2=(\overline{2}+\overline{0})x^3 [/mm] + [mm] (\overline{3}+\overline{4})x^2+(\overline{0}+\overline{2})x+(\overline{4}+\overline{1})x^0=\overline{2}x^3+\overline{2}x^2+\overline{2}x+\overline{0}=\overline{2}x^3+\overline{2}x^2+\overline{2}x.
[/mm]
Kurz gesagt: die passenden Koeffizienten werden addiert.
Komplizierter ist die Multiplikation, in allgemeiner Schreibweise sieht sie geradezu erschreckend aus:
p [mm] \odot q:=\sum_{k=0}^{m+n}\left(\sum_{i+j=k} a_i\cdot b_j\right)x^k.
[/mm]
Was verbirgt sich hierhinter? Die Polynome werden ausmultipliziert so, wie man das aus der Schule vom Multiplizieren von Klammern kennt ("jeder mit jedem"), und dann wird nach Potenzen von x sortiert.
Beispiel:
[mm] p_1\odot p_2=(\overline{2}x^3+\overline{3}x^2 +\overline{4}x^0)\odot(\overline{4}x^2 +\overline{2}x [/mm] + [mm] \overline{1}x^0)
[/mm]
[mm] =(\overline{2}*\overline{4})x^5 [/mm] + [mm] (\overline{2}*\overline{2}+\overline{3}*\overline{4})x^4 [/mm] + [mm] (\overline{2}*\overline{1} [/mm] + [mm] \overline{3}*\overline{2})x^3 [/mm] + [mm] (\overline{3}* \overline{1}+\overline{4}*\overline{4})x^2 [/mm] + [mm] \overline{4}*\overline{2}x^1 [/mm] + [mm] \overline{4}*\overline{1}x^0
[/mm]
[mm] =\overline{3}x^5 +\overline{1}x^4 [/mm] + [mm] \overline{3}x^3+\overline{2}x^2+\overline{3}x^1+\overline{4}x^0.
[/mm]
So, nun haben wir unsere Menge, die Polynome mit Koeffizienten aus [mm] \IZ_5, [/mm] und die beiden Verknüpfungen [mm] \oplus [/mm] und [mm] \odot, [/mm] und Du kannst nun zeigen, daß diese Menge mit diesen Verknüpfungen einen Ring bildet. Tun kannst Du das, indem Du die Ringaxiome nachrechnest.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 12:22 Mo 29.09.2008 | | Autor: | kawu |
Danke, deine Erklärung war sehr aufschlussreich.
Ich vermute, dass ich bei den Polynomen einen Zusammenhang entdeckt habe:
Bei einem Körper [mm]\mathds{K}_{n}[/mm] ist das X in einem Polynom immer n-1 und das Ergebnis der Addition der Koeffizienten ist logischerweise auch immer modulo (n-1) = 0
|
|
|
| |
|
> Ich vermute, dass ich bei den Polynomen einen Zusammenhang
> entdeckt habe:
>
> Bei einem Körper [mm]\mathds{K}_{n}[/mm] ist das X in einem Polynom
> immer n-1 und das Ergebnis der Addition der Koeffizienten
> ist logischerweise auch immer modulo (n-1) = 0
Hallo,
das macht mich etwas ratlos...
Ich verstehe Deine Gedanken nicht.
Nehmen wir nochmal [mm] \IZ_5.
[/mm]
Es ist doch [mm] p:=\overline{4}x^10 [/mm] + [mm] \overline{3}x [/mm] ein Polynom mit Koeffiienten aus [mm] \IZ_5.
[/mm]
Die Summe der Koeffizienten ist 2 (mod 5). Was willst Du sagen über die Summe dieser Koeffizienten?
> Bei einem Körper [mm]\mathds{K}_{n}[/mm] ist das X in einem Polynom immer n-1
Was meinst Du hiermit?
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:25 Mo 29.09.2008 | | Autor: | kawu |
Naja, so ein lateinischer Buchstabe ist in der Mathematik doch (soweit ich das verstanden habe) immer ein Variable, die einen bestimmten wert hat. Für welchen Wert steht [mm]x[/mm] in einem solchen Polynom?
lg, Kawu
|
|
|
| |
|
> Naja, so ein lateinischer Buchstabe ist in der Mathematik
> doch (soweit ich das verstanden habe) immer ein Variable,
> die einen bestimmten wert hat. Für welchen Wert steht [mm]x[/mm] in
> einem solchen Polynom?
Hallo,
Variable hat man in der Mathematik, wenn man verschiedenes einsetzen kann.
In einem Polynom ist das x nur ein formales Zeichen, meist schrebt man X dafür.
Bei einer Polynomfunktion, z.B. [mm] p(x):=\overline{2}x^3 [/mm] + [mm] \overline{1}x +\overline{4} [/mm] (Koeffizienten aus [mm] \IZ_5) [/mm] muß man zunächt einmal drüber sprechen, aus welcher Menge in welche Menge sie abbilden soll.
Was kann man hier für x einsetzen? Sinnvoll wären z.B. Elemente aus [mm] \IZ_5, [/mm] Matrizen über [mm] \IZ_5. [/mm] Es müssen solche Objekte sein, die man mit den Koeffizienten multiplizieren und untereinander addieren kann.
Für [mm] p:\IZ_5 \to \IZ_5 [/mm] mit
[mm] p(x):=\overline{2}x^3 [/mm] + [mm] \overline{1}x +\overline{4} [/mm]
kann man
p( [mm] \overline{0}),
[/mm]
p( [mm] \overline{1}),
[/mm]
p( [mm] \overline{2}),
[/mm]
p( [mm] \overline{3})
[/mm]
p( [mm] \overline{4})
[/mm]
ausrechnen.
(Aber man könnte die Funktion auch so definieren, daß man Matrizen einsetzt.)
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:33 Mo 29.09.2008 | | Autor: | kawu |
Ich kann nicht abstreiten, dass ich jett nur noch Bahnhof verstehe. Allerdings hat mir das auch gezeigt, dass ich mit meiner Sicht der dinge total falsch gelegen habe.
Offenbar sind Polynome nichts, was eine eigenständige Aufgabe darstellen könnte.
Ich würde mich gern weiter mit diesen Dingen beschäftigen und brauche dafür wohl erstmal ein paar andere Vorkenntnisse. Was könntet ihr mir als empfehlenswertes Grundwissen empfehlen, das es mir möglich macht, Polynome zu verstehen?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:50 Di 30.09.2008 | | Autor: | kawu |
Nachdem ich mich jetzt geduldig und aufmerksam mit dieser Lektüre befasst habe, weiß ich leider immer noch nicht, was ein Polynom / Polynomring ist. Das Problem ist jetzt für mich offensichtlich: Diese mathematischen Symbole sind für mich größtenteils unverständlich, da ich die bedeutung einiger schlicht und einfach nicht kenne. Gibt es vielleicht irgendwo eine vollständige Liste mit erklärungen dazu? Könnte mir hier jemand die erklärung eines Polynoms in einer leicht verständlichen, sprachlichen erklärung liefern? Diese Schülerfacharbeit fand ich sehr leicht verständlich, vielleicht lässt sich die bedeutung eines Polynoms in ähnliche Form fassen?
Danke schonmal im Vorraus für die Geduld, die ihr mit mir habt!
KaWu
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:20 Di 30.09.2008 | | Autor: | vivo |
ein beispiel für ein Polynom ist:
f(x) = [mm] 3x^2 [/mm] + 5x - 2
graphisch gesehen ist dies eine nach oben geöffnete Parabel.
ein Polynom ist also allgeimein geschrieben:
P(x) = [mm] \summe_{i=0}^{n} a_i x^i [/mm] = [mm] a_n x^n [/mm] + [mm] a_{n-1} x^{n-1} [/mm] + ... + [mm] a_1 [/mm] x + [mm] a_0
[/mm]
in unserem Beispiel ist n also 2 und [mm] a_2 [/mm] = 3, [mm] a_1 [/mm] = 5 und [mm] a_0 [/mm] = -2
allgemein darf natürlcih [mm] a_i [/mm] auch 0 sein.
gruß
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:11 Di 30.09.2008 | | Autor: | kawu |
Verstehe ich das richtig, dass Geometrie mir dazu verhelfen könnte, Polynome zu verstehen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:53 Di 30.09.2008 | | Autor: | vivo |
nein, eigentlich nicht.
es ist vielmehr so, dass man natürlich jedes polynom in einem kartesischen koordinaten system darstellen kann. es gibt also die wertepaare (x,y) und
z.B.
y = [mm] 2x^2 [/mm] +5x -3
eine nach oben geöffnete Parabel oder
y = 2x+3
eine gerade mit steigung 2
oder
[mm] 3x^7 [/mm] + [mm] 228x^4 [/mm] + 3x -200
dass alles sind polynome mit Koeffizienten aus den reellen Zahlen
willst du die Menge aller dieser Polynome so musst du irgendwie alle hinschreiben dies geht natürlich nur so:
[mm] \summe_{i=0}^{n} a_ix^i [/mm] n [mm] \ge [/mm] 0 , [mm] a_i \in [/mm] IR
das ist dann der Polynomring über IR
mehr gibt es da nicht zu verstehen ...
ich glaube du erwartest irgendwie was anderes ... und kannst es deshalb nicht verstehen ...
vielleicht schreibst du mal was genau du damit eigentlich machen willst .-)
gruß
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:29 Mi 01.10.2008 | | Autor: | kawu |
Das stimmte zumindest am anfang, mitlerweile hat sich aber mein vorrat an spekulationen, was ein polynom sein könnte, erschöpftf.
schau dir mal das an:
http://www.csrc.nist.gov/publications/fips/fips197/fips-197.pdf
Dort gibt es einige mathematische erläuterungen zum AES-Algorithmus (Kryptographie). Da wird auch ein Polynom erwähnt.
Wofür ich das brauche? Das ist gut, denn ich BRAUCHE es eigentlich nicht. Mich wurmt es nur, dass ich es nicht verstehe und deswegen wollte ich das ändern.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:37 Mi 01.10.2008 | | Autor: | vivo |
hi,
ok wenn du dir die antwort von pelzig genau durchliest, findest du alles was du brauchst um das polynom in diesem artikel über den algorithmus zu verstehen.
gruß
|
|
|
| |
|
Hallo kawu,
du hast dir hier jedenfalls ein sehr interessantes Gebiet
herausgepickt, in dem man viel über die mathematischen
Zusammenhänge lernen kann, die manchmal - trotz der
abstrakten Strukturen, die man dabei benützt - zu über-
raschenden Anwendungen führen, die sogar in vielen
Geräten eingebaut sind, die wir nutzen, auch wenn wir
keinen blassen Schimmer von der raffinierten Mathematik
haben, die sich darin versteckt.
Um dich über Galois-Körper (GF steht für "Galois Field" und
Field steht auf englisch für das, was wir in der Algebra einen
Körper nennen) schlau zu machen, könntest du bei dieser
Seite nachschauen:
![[]](/images/popup.gif) Arithmetik in endlichen Körpern
Dort werden auch konkrete Beispiele in der Art gezeigt,
wie du sie wohl suchst. In [mm] GF(2^8) [/mm] herrscht eine sehr
einfache Arithmetik, die sich sofort in Computerchips
realisieren lässt, weil z.B. 1+1=0 gilt. Nehmen wir ein
Beispiel einer Multiplikation:
Hex:
4D*0B = ?
Als Bitfolgen:
01001101*00001011
Als Polynome:
[mm] (x^6+x^3+x^2+1)*(x^3+x+1)
[/mm]
ausmultipliziert:
[mm] x^9+x^7+2x^6+x^5+x^4+3x^3+x^2+x+1
[/mm]
gliedweise mod 2 reduziert:
[mm] x^9+x^7+x^5+x^4+x^3+x^2+x+1
[/mm]
wieder als Bitfolge:
1010111111
Nun gibt es aber einen Überlauf, die Bitfolge ist zu
lang (sie darf maximal 8 Bits umfassen). Nun kommt die
Reduktion nach Rijndael: es wird der Rest des Polynoms
[mm] x^9+x^7+x^5+x^4+x^3+x^2+x+1 [/mm]
bei der Division durch das Polynom
[mm] x^8+x^4+x^3+x+1
[/mm]
gebildet. Diese Polynomdivision geht überraschend leicht,
probier' s einfach aus:
[m](x^9+x^7+x^5+x^4+x^3+x^2+x+1)\ :\ (x^8+x^4+x^3+x+1)\ =\ x[/m], Rest [m](x^7+x^3+1)[/m] (***)
Der Rest ist das Resultat, wieder als Bitfolge:
10001001
Hex:
89
Während meines Studiums machte ich einmal ein Industrie-
praktikum, in dem ich meine gerade erworbenen Kenntnisse
über solche Körper umsetzen konnte für ein neu zu ent-
wickelndes Verschlüsselungssystem. Das war hochinteressant.
LG al-Chw.
(***) danke informix für die kleine Korrektur !
|
|
|
| |
|
| Status: |
(Korrektur) kleiner Fehler  | | Datum: | 13:20 Do 02.10.2008 | | Autor: | informix |
Hallo Al-Chwarizmi,
Super Erklärung, da hat sich die Warterei gelohnt. ![[super]](/images/smileys/super.gif "[super]")
Einen kleinen Schreibfehler könntest du verbessern - der besseren Lesbarkeit wegen...
>
> Nun gibt es aber einen Überlauf, die Bitfolge ist zu
> lang (sie darf maximal 8 Bits umfassen). Nun kommt die
> Reduktion nach Rijndael: es wird der Rest des Polynoms
>
> [mm]x^9+x^7+x^5+x^4+x^3+x^2+x+1[/mm]
>
> bei der Division durch das Polynom
>
> [mm]x^8+x^4+x^3+x+1[/mm]
>
> gebildet. Diese Polynomdivision geht überraschend leicht,
> probier' s einfach aus:
>
> [m](x^9+x^7+x^5+x^4+x^3+x^2+x+1)\ :\ (x8 + x4 + x3 + x + 1)\ =\ x[/m],
> Rest [m](x^7+x^3+1)[/m]
besser:
[m](x^9+x^7+x^5+x^4+x^3+x^2+x+1)\ :\ (x^8 + x^4 + x^3 + x + 1)\ =\ x[/m],
Rest [m](x^7+x^3+1)[/m]
> Während meines Studiums machte ich einmal ein Industrie-
> praktikum, in dem ich meine gerade erworbenen Kenntnisse
> über solche Körper umsetzen konnte für ein neu zu ent-
> wickelndes Verschlüsselungssystem. Das war
> hochinteressant.
>
>
> LG al-Chw.
>
einfach interessant, wie sich so abstrakte Mathematik in der Realität wieder findet! Darum liebe ich mein Fach so!
Gruß informix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:56 Do 02.10.2008 | | Autor: | kawu |
Es ist leicht gesagt, dass es einfach ist. Ich glaube, die Division scheint der letzte große Meilenstein zu sein, der mir noch nicht ganz klar ist.
Habe mir schon die Erklärung zu "finite fields" und der Multiplikation angesehen, aber einen Sinn ergibt das für mich nicht. :(
|
|
|
| |
|
> Es ist leicht gesagt, dass es einfach ist. Ich glaube, die
> Division scheint der letzte große Meilenstein zu sein, der
> mir noch nicht ganz klar ist.
>
> Habe mir schon die Erklärung zu "finite fields" und der
> Multiplikation angesehen, aber einen Sinn ergibt das für
> mich nicht. :(
Wenn du die Polynomdivision noch nicht kennst, musst
du dich zuerst damit beschäftigen. Dazu findest du sicher
viel Material im Netz. Es gibt z.B. eine Übungsseite mit
Hilfen:
http://www.arndt-bruenner.de/mathe/scripts/polynomdivisionueben.htm
Ein kleines Beispiel:
Weil [mm] (x+3)*(x^2-x+2)=x^3+2x^2-x+6
[/mm]
muss natürlich gelten: [mm] (x^3+2x^2-x+6)/(x+3) [/mm] = [mm] x^2-x+2
[/mm]
Wie findet man aber diesen Quotienten, wenn er nicht
schon vorliegt ?
Man geht schrittweise vor wie beim schriftlichen Dividieren
von mehrstelligen Dezimalzahlen.
Hat man die Aufgabe
[mm] (x^3+2x^2-x+6)/(x+3)=?
[/mm]
vor sich, dividiert man zuerst die vordersten Glieder
(die mit den höchsten Exponenten), hier also
[mm] x^3/x. [/mm] Das ergibt [mm] x^2; [/mm] dies schreibt man als vorläufiges
Resultat auf:
[mm] (x^3+2x^2-x+6)/(x+3) [/mm] = [mm] x^2 [/mm] (+.....)
Man multipliziert den Divisor mit diesem [mm] x^2, [/mm] schreibt
das Produkt geordnet unter den Dividenden und subtrahiert
es von diesem:
[mm] (x^3+2x^2-x+6)/(x+3) [/mm] = [mm] x^2 [/mm] (+.....)
[mm] x^3+3x^2
[/mm]
___________
[mm] -x^2-x+6
[/mm]
Man muss diesen Rest noch durch (x+3) teilen und
fängt wieder vorne an: [mm] (-x^2)/x=-x
[/mm]
Dieses -x fügt man dem vorläufigen Ergebnis zu
und muss wieder den Divisor mit diesem zweiten
Teilergebnis multiplizieren und dieses Produkt
vom aktuellen Rest subtrahieren:
[mm] (x^3+2x^2-x+6)/(x+3) [/mm] = [mm] x^2 [/mm] -x (+.....)
[mm] x^3+3x^2
[/mm]
___________
[mm] -x^2-x+6
[/mm]
[mm] -x^2-3x
[/mm]
________
2x+6
nächster Schritt: (2x):x=2
[mm] (x^3+2x^2-x+6)/(x+3) [/mm] = [mm] x^2 [/mm] -x +2
[mm] x^3+3x^2
[/mm]
___________
[mm] -x^2-x+6
[/mm]
[mm] -x^2-3x
[/mm]
_______
2x+6
2x+6
____
0
Da der Rest 0 ist, ist diese Division ohne Rest
aufgegangen.
LG
|
|
|
| |
|
Hallo kawu,
> Seit einigen Tagen befasse ich mich nun mit endlichen
> Körpern und um es gleich zu sagen: ich beschäftige mich
> damit aus persönlichem Interesse und nicht, weil ich in der
> Schule oder sonst wo verlangt wird, dass ich das verstehe
> (das scheint hier von großer Bedeutung zu sein, da man
> sonst an den Mathelehrer verwiesen wird *g*)
Kannst du uns vielleicht bitte erklären, welches deine Vorkenntnisse sind?
Welche Körper hast du denn bislang kennengelernt?
ein-zwei Beispiele (möglichst unterschiedlich) genügen.
Weißt du, was ein Polynom ist?
Wikipedia ist da eine gute Anlaufstelle.
Weißt du, was ein Ring im Vergleich zu einem Körper ist - kannst du die Unterschiede in Kurzform benennen?
Deine Background-Angabe "Hauptschule" lässt darauf schließen, dass du vergleichbares nicht in der Schule gelernt hast. Wo dann?
> Um zum Problem zu kommen: Ich verstehe weder, was ein
> Polynomring bewikt, noch was man mit ihm macht. Schon den
> ganzen Tag befasse ich mich damit und habe fleißig gesucht,
> stolpere aber nur über kryptische Formeln, die den Anschein
> erwecken, dass sie eher für die Leser gedacht sind, die
> schon wissen, was Polynomringe sind.
>
> Könnte mir hier jemand, auch wenn das mehr als unüblich
> ist, an einem Beispiel erklären, was Polynomringe sind?
>
> Danke schonmal an alle, die mir behilflich sein können und
> wollen!
> Kawu
Gruß informix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:57 Mo 29.09.2008 | | Autor: | kawu |
Das ist richtig, in der Schule habe ich das tatsächlich nicht gelernt. Ich fing vor einigen Tagen an, mich mit Kryptografie zu beschäftgen und stieß recht schnell auf den AES-Algorithmus (Rijndael). Den mit einer Programmiersprache zu implementieren, ist zwar recht leicht, allerdings würde ich mich auch gern mit den Theoretischen Details auskennen. Im Rijndael-Algorithmus wird der Körper [mm]GF(2^{8})[/mm] verwendet. was das für folgen auf Addition bei diesem Körper hat, ist sehr einfach. Mit der Multiplikation siht es da schon komplizierter an (und da kamen bei mir zum ersten mal die Polynome ins Spiel). Ich habe mir ein Buch zu diesem Thema beschafft: "Endliche Körper - verstehen, rechnen, anwenden" aus dem Springer-Verlag. Die ansätze habe ich auch sehr schnell verstanden, allerdings ist es extrem schwer, sich eine Vorstellungen von Polynomringen zu machen, wenn man nicht einmal weiß, was ein einzelnes Polynom ist und wofür man es braucht oder gar seinen Sinn und Zweck falsch verstanden hat. Deine Links werde ich mir mal ansehen, die Schülerfacharbeit sieht sehr Detailiert aus. Dafür möchte ich mich schonmal im Vorraus bedanken!
lg, Kawu
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:09 Di 30.09.2008 | | Autor: | pelzig |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Also zunächst einmal, diese Begriffe... Ring, Körper... sind erstmal was ganz und gar unanschauliches. Es ist eine Menge von Dingen, mit den man rumrechnen kann. Weiter nichts. Man kann sie nicht hinmalen, sie existieren nur in unserem Kopf. Je nachdem nach welchen Gesetzen man dadrin rumrechnen kann, heißen diese seltsamen Dinger z.B. Gruppe, Monoid, unitärer Ring, Schiefkörper, ... - es gibt ne ganze Menge davon. In der Schule wirst du wahrscheinlich niemals davon hören, aber Mathematiker denken praktisch nur noch in solchen "Strukturen".
Du musst wissen was ein Ring ist, um Polynomringe zu verstehen. Schau dir am besten die Seiten auf Wikipedia oder so an.
So, nun weißt du was Ringe sind (!), zurück zum Thema. Wenn man einen Ring $R$ hat, kann man daraus einen eine neuen Ring , den "Polynomring" bauen. Dazu müssen wir nur folgende Sachen erklären:
1) Was sind die Objekte in unserem "Poylnomring"? (Das ist nur ein Name, wir können es auch "Affenhaus" nennen, aber das wäre kein guter Name...)
2) Wie funktioniert die Addition (also die Operation $\oplus$)?
3) Wie funktioniert die Multiplikation (... $\odot$)?
zu 1) Wir definieren uns: Ein Polynom ist eine Folge $(a_n)_{n\in\IN}$ von Elementen aus $R$, bei der nur endlich viele Folgenglieder von $0$ verschieden sind. Unser Polynomring ist dann die Menge all dieser "Polynome", wir schreiben $R[x]$.
zu 2) Ok wir haben definiert was die Dinger in unserem Polynomring sein sollen, wie zum Henker addiert man die jetzt? Wir definieren $(p\oplus q)_n:=p_n+q_n$.
Das bedeutet: wenn man zwei Polynome $p,q$ hat, dann kann man $p\oplus q$ bilden, indem man einfach die ganzen Folgenglieder gliedweise addiert (das ist die Addition aus $R$!). Wir müssen sichergehen dass dabei nicht plötzlich etwas entsteht, das gar kein Polynom ist. Da $R$ ein Ring ist, ist für jedes $n\in\IN$ auch $p_n+q_n\in R$, also ist diese oben definierte "Summe" schonmal eine Folge von Elemente aus $R$, aber sind auch wirklich nur endlich viele von Null verschieden? Ja, denn hätte $p\oplus q$ unendlich viele von $0$ verschiedene Folgenglieder, dann hätte auch $p$ oder $q$ unendlich viele gehabt, was nicht sein kann da $p$ und $q$ Polynome sind.
zu 3) (Mach ich jetzt mal etwas kürzer) Wir definieren die Multiplikation: $(p\odot q)_n:=\sum_{j=0}^np_jq_{n-j}$. Mach dir klar dass auch diese Operation wirklich aus zwei Polynomen ein Polynom macht.
Jetzt haben wir also eine Menge mit der wir rumrechnen können. Es bleibt zu zeigen dass dies auch wirklich ein Ring ist, d.h. dass die Rechenregeln, wie z.B. Kommutativität der $\oplus$-Operation, wirklich gelten. Zur Übung kannst du das ja mal nachrechnen, besonders leicht sind die Gruppen-Axiome von $\oplus$.
Polynome sind also nichts weiter als Zahlenfolgen, mit den man rumrechnen kann.
Jetzt kommt etwas sehr wichtiges. Aus einem Polynom $p\in R[x]$ kann man auf sehr natürliche Weise eine Funktion $\hat{p}$ bauen, die Elemente aus $R$ auf Elemente aus $R$ abbildet, indem man definiert: $\overline{p}(x):=\sum_{j=0}^\infty p_jx^j$. Dies ist natürlich in Wirklichkeit eine endliche Summe, da ja nur endlich viele $p_j$ verschieden von $0$ sind. Dieses $\overline{p}$ ist eine sog. Polynomfunktion. Es ist kein Polynom im streng mathematischen Sinne, sondern etwas ganz anderes.
Aus der Schule kennst du auch "Polynome", z.B. die schöne Parabel $f(x)=x^2+1$, das ist eben eine solche Polynomfunktion - das zugehörige Polynom wäre die Folge $1,0,1,0,0,...$.
Wenn man hier mal ein bischen nachdenkt erkennt man auch, warum man die Polynommultiplikation so "kompliziert" definiert hat, es gilt nämlich $(\overline{p\odot q})(x)=\overline{p}(x)\cdot\overline{q}(x)$!!! Mach dir klar was diese Gleichung eigentlich aussagt, was ist der unterschied zwischen rechter und linker Seite...?
Warum die ganze Mühe? Der Punkt ist, dass die wesentliche Struktur von Polynomfunktionen durch das zugehörige Polynom bereits vollständig gegeben ist. Es ist völlig egal was unsere Polynomfunktion macht, kenne ich das zugehörige Polynom, weiß ich bereits alles. In den reellen Zahlen sind Polynome und Polynomfunktionen tatsächlich dasselbe in dem Sinne, das man jeder Polynomfunktion auch nur ein zugehöriges Polynom zuordnen kann, deshalb lernt man diesen feinen Unterschied in der Schule nicht.
Wenn man aber "exotische" Ringe als Ausgangspunkt wählt, ändert sich die Situation schlagartig. Zum Beispiel $R=\IZ_2$, also die Ganzen Zahlen modulo $2$ (das ist sogar ein Körper...). Hier gibt es Polynome, die unterschiedlich sind, aber die gleiche Polynomfunktion haben, z.B: $p:1,0,1,0,0,0,...$ und $q:1,1,0,0,0,...$. Offensichtlich sind die Polynome verschieden, aber die zugehörigen Polynomfunktionen sind gleich (nachrechnen!).
Bei endlichen Ringen passiert das immer, da es einfach viel Mehr Polynome (nämlich unendlich viele) als Funktionen gibt (nämlich $n^n$, wobei $n$ die Anzahl der Elemente des Ringes ist). Da jede Polynomfunktion eine Funktion ist, muss es also Polynomfunktionen geben, denen man mehrere Polynome zuordnen kann.
Damit sollte dir nun klar sein das ein Polynomring etwas sehr einfaches, aber trotzdem etwas unanschaulich ist. Insbesonder hat es nix mit Geometrie zu tun.
Gruß,
Robert
Anmerkung: Natürlich schreibt kein Mensch Polynome wirklich als Zahlenfolgen hin, ich habe das hier nur gemacht damit du nicht unterwegs vergisst, was der Unterschied zwischen Polynomen und Polynomfunktionen war. Man definiert dazu folgende Polynome:
Für beliebiges $a\in R$ ist $aX^0$ das Polynom mit der Folge $a,0,0,0,...$.
Weiter ist $X$ das Polynom mit der Folge $0,1,0,0,0,...$.
Damit kann man für $n\in\IN$ das Polynom $X^n$ definieren als
$\underbrace{X\cdot X\cdot ... \cdot X}_{n\text{-mal}$
Man kann leicht zeigen, dass dann $X^n$ die Folge ist, die an der Stelle $n$ eine $1$ und sonst nur Nullen hat.
Damit lässt sich nun jedes Polynom $(p_n)_{n\in\IN}$ schreiben als $\sum_{j}p_jX^j$.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:39 Mi 01.10.2008 | | Autor: | kawu |
danke für deine lange und ausführliche erklärung. dass ich es jetzt immernoch nicht verstanden habe, treibt dich jetzt hoffentlich nicht in die verzweifelung. inzwischen habe ich mir mal die englische wikipedia-seite zu dem thema angesehen, nun weiß ich wenigstens, warum und wann ein polynom "polynom x-xten grades heißt" und was an einem term der quotient ist. was die quotienten innerhalb eines polynoms bewirken, weiß ich allerdings noch nicht.
irgendwie dachte ich mir, dass so ein polynom dazu verwendet werden kann, ein "greifbares" ergebnis zu liefern, dass ein polynom eine art von rechenweg ist. damit habe ich mich wohl geirrt oder?
ab [mm](a_n)_{n\in\IN}[/mm] verstehe ich bei der erklärung garnichts mehr, ich weiß nicht, wofür n steht. ich habe noch einmal sichergestellt, dass ich alles wissenswerte über ringe und körper weiß, was wikipedia hergibt (dem war so) aber auf polynome kann ich mir absolut nichts einbilden.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:48 Mi 01.10.2008 | | Autor: | pelzig |
> danke für deine lange und ausführliche erklärung. dass ich
> es jetzt immernoch nicht verstanden habe, treibt dich jetzt
> hoffentlich nicht in die verzweifelung. inzwischen habe ich
> mir mal die englische wikipedia-seite zu dem thema
> angesehen, nun weiß ich wenigstens, warum und wann ein
> polynom "polynom x-xten grades heißt" und was an einem term
> der quotient ist. was die quotienten innerhalb eines
> polynoms bewirken, weiß ich allerdings noch nicht.
>
> irgendwie dachte ich mir, dass so ein polynom dazu
> verwendet werden kann, ein "greifbares" ergebnis zu
> liefern, dass ein polynom eine art von rechenweg ist. damit
> habe ich mich wohl geirrt oder?
Der einfachste Weg in der Mathematik ist es meistens, nicht nach der Anwendung zu fragen... Meine Antwort war aber auch sehr abstrakt. Aber da du deine Frage in einem abstrakten Kontext gestellt hast (AES... hab auch keine Ahnung davon) hab ich gedacht es hilft dir vielleicht was.
> ab [mm](a_n)_{n\in\IN}[/mm] verstehe ich bei der erklärung garnichts
> mehr, ich weiß nicht, wofür n steht. ich habe noch einmal
> sichergestellt, dass ich alles wissenswerte über ringe und
> körper weiß, was wikipedia hergibt (dem war so) aber auf
> polynome kann ich mir absolut nichts einbilden.
[mm] $(a_n)_{n\in\IN} [/mm] $ ist die Schreibeweise für Zahlenfolgen. Das bedeutet, zu jeder natürlichen Zahl $n$, z.B. $5$ oder $10001$ hat man ein Element [mm] $a_n$ [/mm] ("Das n-te Folgenglied"), in dem Fall [mm] $a_5$ [/mm] bzw. [mm] $a_{10001}$. [/mm] Zum Beispiel gibt es die Folge [mm] $a_n:=n$, [/mm] dann ist [mm] $a_0=0$, $a_1=1$, $a_2=2$ [/mm] und so weiter, die Folge sieht also so aus: $0,1,2,3,4,5,...$.
Aber okay... das allein wird dich wahrscheinlich auch nicht erleuchtet haben. Schau dir auch die anderen Antworten nochmal an und stell weiter Fragen wenn du etwas nicht verstehst. Es führt leider in der Mathematik kein Weg dran vorbei es immer wieder zu versuchen und die richtigen Fragen zu stellen.
Gruß, Robert
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:25 Mi 01.10.2008 | | Autor: | kawu |
Ok, in dem Fall sollte ich (und das werde ich sicher, indem ich mich nur lang genug mit dieser Materie befasse) lernen, die richtigen Fragen zu stellen. Durch deinen Letzten erklärungsversuch gehe ich einfach mal davon aus, dass sich die Geduld mit mir noch lange nicht der Erschöpfung geneigt hat.
Aber die Frage, die ich mir im Moment stelle, ist, was ich da Fragen soll. Ich habe nichtmal im Ansatz eine Ahnung von dem Sinn und dem Nutzen von Polynomen im Praktischen Umfeld.
Das, was ich bisher in dieser Hinsicht gefunden habe, ist dies: http://www.mathe1.de/mathematikbuch/funktionen_daspolynom_160.htm
Auf dieser Internetseite habe ich bisher immer ein paar sinnvolle Informationen bekommen. Aber in diesem Punkt sind die Erklärungen (zumindest so wie ich das sehe) mehr als Dürftigt. Dort wird zwar in den ersten Zeilen ein Polynom gezeigt aber dann nur noch die lineare Algebra behandelt, die ich schon aus der Schule kenne (und ich bin mir sicher, dass in all den Jahren damals nicht einmal das Wort "polynom" gefallen ist).
Was könnte man denn mir als Anfänger empfehlen, mit dem ich mich langsam an dieses Thema herantasten kann?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:58 Mi 01.10.2008 | | Autor: | pelzig |
> Aber die Frage, die ich mir im Moment stelle, ist, was ich
> da Fragen soll. Ich habe nichtmal im Ansatz eine Ahnung von
> dem Sinn und dem Nutzen von Polynomen im Praktischen
> Umfeld.
Wie gesagt, der "Sinn und Nutzen" ist vom mathematischen Standpunkt erstmal uninteressant.
Die Frage ist doch, wie du überhaupt auf dieses Problem gestoßen bist. Wenn AES dein Problem ist, solltest du dich nicht mehr als nötig mit Polynomen beschäftigen. Versuche stattdessen rauszufinden, was sie mit den Polynomen in deinem Buch (oder was auch immer) machen.
> Das, was ich bisher in dieser Hinsicht gefunden habe, ist
> dies:
> http://www.mathe1.de/mathematikbuch/funktionen_daspolynom_160.htm
>
> Auf dieser Internetseite habe ich bisher immer ein paar
> sinnvolle Informationen bekommen. Aber in diesem Punkt sind
> die Erklärungen (zumindest so wie ich das sehe) mehr als
> Dürftigt. Dort wird zwar in den ersten Zeilen ein Polynom
> gezeigt aber dann nur noch die lineare Algebra behandelt,
> die ich schon aus der Schule kenne (und ich bin mir sicher,
> dass in all den Jahren damals nicht einmal das Wort
> "polynom" gefallen ist).
Vergiss die Seite.
> Was könnte man denn mir als Anfänger empfehlen, mit dem ich
> mich langsam an dieses Thema herantasten kann?
Wie gesagt, es kommt darauf an wieviel Wissen du brauchst. Fast alles was man als Anfänger über Polynome wissen sollte steht bereits in diesem Thread.
Aus jedem Ring kann man den zugehörigen Polynomring konstruieren, die Elemente heißen Polynome. Jedem Polynom kann man die zugehörige Polynomfunktion zuordnen.
Ansonsten halt der Wikipedia-Artikel, besonders der Abschnitt über Polynome in der abstrakten Algebra.
Gruß, Robert
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:31 Do 02.10.2008 | | Autor: | kawu |
Ok, das ist ein vernünftiger Ansatzpunkt. Nehmen wir also mal als Grundlage das FIPS-197 Dokument: http://www.csrc.nist.gov/publications/fips/fips197/fips-197.pdf
Dort wird in Abschnitt 4 auf die "Mathematical Preliminaries" eingegangen. In Abschied 3.2 (Bytes) wurde schon einmal die Polynomschreibweise verwendet. Da in der Informatik alle Bits eines Bytes mit 0 (Least-Significant-Bit) bis 7 (Most-Significant-Bit) adressiert werden, dachte ich zuerst, dass so ein Polynom einfach eine spezielle Schreibweise für die Bits wäre.
(Wer sich auf diese Begriffe nichts einbilden kann, möge einfach fragen)
Hätte dieser erste Gedanke gestimmt, wäre folgendes Polynom
[mm]x^7 + x + 1[/mm]
das folgene Byte in hexadezimaler Schreibweise abgeben: 83 (dezimal: 131, binär: 10000011)
Nachdem ich nun stundenlang versucht habe, die Multiplikation mit dieser Annahme als Grundlage durchzurechnen, musste ich einsehen, dass da irgendwas fehlerhaft ist.
Eine wichtige eigenschaft des Bytes ist aber, dass es eine Zahl zwischen 0 und 255 darstellen kann. Mathematisch könnte man das vielleicht so ausdrücken:
[mm]\mathds{B} = \left\{0, 1, 2, ..., 255\right\}[/mm]
In der Informatik spricht man von einem Überlauf, sobald durch eine mathematische Operation das fassungsvermögen eines Datentyps überschritten wird. Bei einem Byte wäre das
[mm]254 + 8 = 6[/mm]
In der Mathematik könnte man so ein Ergebnis erreichen, indem man nach der Addition Modulo 256 rechnet.
Das sind also nun die grundlegenden mathematischen Eigenschaften eines Bytes, die hier eine Rolle spielen sollten.
Bei der eigentlichen Multiplikation möchte ich mich aber so weit wie möglich von Begriffen wie Bits und Bytes lösen (für die eigentliche Implementierung habe ich schon in der letzten Woche einen Weg gefunden) und mich auf die mathematischen Grundlagen konzentrieren:
Unter Punkt 4.2 wird in dem fips-Dokument gezeigt wie die Zahlen 57 und 83 (hexadezimale Schreibweise) multipliziert werden. Welcher Logik diese Rechnung folgt, entzieht sich meiner Vorstellungskraft. Ich glaube, hier ist eine Frage nach dem WIE nicht zu abstrakt, oder? Kann mir das hier jemand erklären?
|
|
|
| |
|
Hallo kawu,
jetzt wird mir allmählich klarer, wo deine Problem liegen könnten.
> Ok, das ist ein vernünftiger Ansatzpunkt. Nehmen wir also
> mal als Grundlage das FIPS-197 Dokument:
> http://www.csrc.nist.gov/publications/fips/fips197/fips-197.pdf
>
>
> Dort wird in Abschnitt 4 auf die "Mathematical
> Preliminaries" eingegangen. In Abschied 3.2 (Bytes) wurde
> schon einmal die Polynomschreibweise verwendet. Da in der
> Informatik alle Bits eines Bytes mit 0
> (Least-Significant-Bit) bis 7 (Most-Significant-Bit)
> adressiert werden, dachte ich zuerst, dass so ein Polynom
> einfach eine spezielle Schreibweise für die Bits wäre.
>
> (Wer sich auf diese Begriffe nichts einbilden kann, möge
> einfach fragen)
>
>
> Hätte dieser erste Gedanke gestimmt, wäre folgendes
> Polynom
>
> [mm]x^7 + x + 1[/mm]
>
> das folgene Byte in hexadezimaler Schreibweise abgeben: 83
> (dezimal: 131, binär: 10000011)
>
> Nachdem ich nun stundenlang versucht habe, die
> Multiplikation mit dieser Annahme als Grundlage
> durchzurechnen, musste ich einsehen, dass da irgendwas
> fehlerhaft ist.
>
[...]
> Unter Punkt 4.2 wird in dem fips-Dokument gezeigt wie die
> Zahlen 57 und 83 (hexadezimale Schreibweise) multipliziert
> werden. Welcher Logik diese Rechnung folgt, entzieht sich
> meiner Vorstellungskraft. Ich glaube, hier ist eine Frage
> nach dem WIE nicht zu abstrakt, oder? Kann mir das hier
> jemand erklären?
>
Fangen wir erstmal mit der  Addition der Polynome an:
[Dateianhang nicht öffentlich]
Addiere die beiden Polynome, ohne an die spezielle Bedeutung zu denken:
[mm] (x^6+x^4+x^2+x+1)+(x^7+x+1)=x^7+x^6+x^4+x^2+2x+2
[/mm]
nun musst du die letzten beiden Summanden wieder als Bitrechnung interpretieren, bei der ja keine 2-er vorkommen können:
polynomial bei reellen Zahlen: x+x=2x binomial: 10+10=100 polynomial bei Bits: [mm] x+x=x^2
[/mm]
edit: es muss heißen (danke Robert):
polynomial bei reellen Zahlen: x+x=2x binomial: 10+10=00 polynomial bei Bits: x+x=0
polynomial bei reellen Zahlen: 1+1=2 binomial: 1+1=0 polynomial bei Bits: 1+1=0
Damit hast du eine Erklärung für die Rechnung in dem Skript.
Jetzt überlege, wie man die Multiplikation in gleicher Weise "übersetzen" kann. Das Beispiel steht ja in dem Skript.
Auf diese Weise wirst du dann zeigen, dass die bitweise Addition und Multiplikation definiert sind und die Ergebnisse wieder als Bits interpretiert werden können.
Damit bildet die Menge der Bits zusammen mit solcherart definierter Additon und Multiplikation einen Ring, analog zu Polynomringen, die man als Struktur in der abstrakten Mathematik schon lange untersucht.
Das bedeutet, dass man alle Eigenschaften, Gesetze etc. der Polynomringe auch auf diese speziellen Polynome anwenden kann. Hierdurch kann du entdecken, dass die Beschäftigung mit der abstrakten Struktur von "Dingen" neue Erkenntnisse bringen kann, die dann "in der Wirklichkeit" irgendwo neue Erkenntnisse bringen kann.
Frag' nach, wenn ich nun selbst zu abstrakt geworden bin.. 
Gruß informix
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:59 Do 02.10.2008 | | Autor: | kawu |
Die Addition glaube ich verstanden zu haben. An ein paar Anderen Bytes werde ich das später noch einmal üben. Das Ergebnis der Addition kann ich ja ganz einfach auf Richtigkeit prüfen, indem ich die zu addierenden Bytes XOR verknüpfe.
Bei der Multiplikation ist mir etwas aufgefallen, das ich zuvor nie bemerkt habe: Jeder Term des ersten Polynoms wird für jeden Term des zweiten Polynoms aufgeschrieben, der Exponent ist die Summe der beiden Exponenten. Aus dem Polynom, das auf diese Weise entstanden ist, wird nun ein weiteres Polynom (sollte ein Term mit einem gleichen Exponenten doppelt sein, wird er weggelassen, da die addition modulo 2 ist). Bei dem Modulo komme ich nicht weiter. Das ireduzible Polynom (0x11b) ist, so habe ich eben festgestellt, eine Primzahl. Ich nehme an, das muss so sein, da es sonst zu Nullteilern kommen würde, und das darf es ja im Körper nicht.
Könnte mir vielleicht noch jemand das mit dem Modulo erklären?
|
|
|
| |
|
> Die Addition glaube ich verstanden zu haben. An ein paar
> Anderen Bytes werde ich das später noch einmal üben. Das
> Ergebnis der Addition kann ich ja ganz einfach auf
> Richtigkeit prüfen, indem ich die zu addierenden Bytes XOR
> verknüpfe.
>
> Bei der Multiplikation ist mir etwas aufgefallen, das ich
> zuvor nie bemerkt habe: Jeder Term des ersten Polynoms wird
> für jeden Term des zweiten Polynoms aufgeschrieben, der
> Exponent ist die Summe der beiden Exponenten.
Das ist die gewöhnliche Multiplikation von Polynomen.
Natürlich ist [mm] x^m*x^n=x^{m+n} [/mm] und es gelten
für Addition und Multiplikation zunächst die üblichen
Rechenregeln.
> Aus dem
> Polynom, das auf diese Weise entstanden ist, wird nun ein
> weiteres Polynom (sollte ein Term mit einem gleichen
> Exponenten doppelt sein, wird er weggelassen, da die
> addition modulo 2 ist).
Allgemeiner: Potenzen mit geradem Vorfaktor fallen
raus, ungerade Vorfaktoren werden zu 1 reduziert.
> Bei dem Modulo komme ich nicht
> weiter. Das irreduzible Polynom (0x11b)
(???) das entspricht nicht dem von Rijndaal ... ![[notok]](/images/smileys/notok.gif "[notok]")
sorry, es stimmt doch !
ich habe nicht beachtet, dass in dem Polynom auch [mm] \red{x^8} [/mm] vorkommt
> ist, so habe ich
> eben festgestellt, eine Primzahl. Ich nehme an, das muss so
> sein, da es sonst zu Nullteilern kommen würde, und das darf
> es ja im Körper nicht.
Da bin ich nicht so sicher. Die Primzahleigenschaft in [mm] \IZ
[/mm]
hat mit Teilbarkeitseigenschaften in einem Galoiskörper
nicht unbedingt zu tun.
> Könnte mir vielleicht noch jemand das mit dem Modulo
> erklären?
Damit kommen wir schon zu einem Thema, das eindeutig
Hochschulmathe ist. Schau z.B. einmal da nach:
http://de.wikipedia.org/wiki/Irreduzibles_Polynom
Irreduzibles Polynom
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:57 Do 02.10.2008 | | Autor: | pelzig |
Das Modulo-Rechnen mit Polynomen geht prinzipiell mit Polynomdivision. Beachte, dass du dabei nach wie vor alle Rechnungen im Körper [mm] $\IZ_2$, [/mm] also modulo $2$ durchführen musst.
Gruß, Robert
|
|
|
| |
|
Hallo kawu,
> Hallo!
>
> Seit einigen Tagen befasse ich mich nun mit endlichen
> Körpern und um es gleich zu sagen: ich beschäftige mich
> damit aus persönlichem Interesse und nicht, weil ich in der
> Schule oder sonst wo verlangt wird, dass ich das verstehe
> (das scheint hier von großer Bedeutung zu sein, da man
> sonst an den Mathelehrer verwiesen wird *g*)
>
> Um zum Problem zu kommen: Ich verstehe weder, was ein
> Polynomring bewikt, noch was man mit ihm macht. Schon den
> ganzen Tag befasse ich mich damit und habe fleißig gesucht,
> stolpere aber nur über kryptische Formeln, die den Anschein
> erwecken, dass sie eher für die Leser gedacht sind, die
> schon wissen, was Polynomringe sind.
>
> Könnte mir hier jemand, auch wenn das mehr als unüblich
> ist, an einem Beispiel erklären, was Polynomringe sind?
>
![[guckstduhier]](/images/smileys/guckstduhier.gif "[guckstduhier]") Polynom in unserem SchulMatheLexikon.
Gruß informix
|
|
|
|
