Interpolation im GF[x]

Neue Frage »

09.05.2005, 00:10	Mantisse	Auf diesen Beitrag antworten »
Interpolation im GF[x] Hallo. Ich soll eine Polynominterpolation nach Newton sowie nach LaGrange im GF[29] berechnen. Allerdings wird in beiden Verfahren ja die Division benutzt. Ich habe diese Stützpunkte hier: (3,12) , (15,1) , (17,16) Wenn ich jetzt nach LaGrange vorgehe, dann folgt daraus: $\begin{eqnarray} L_0(x) := \frac{(x-15)(x-17)}{(3-15)(3-17)} \equiv \frac{x^2 - 15x - 17x + 9}{17 15} \equiv \frac{x^2 + 26x + 9}{9} \equiv \frac{1}{9} * (x^2 + 26x + 9) \end{eqnarray}$ Allerdings habe ich so meine Probleme mit rechnen im GF[x] und Brüchen. Mein Tutor sagte, dass es bei ,- und + Operationen egal ist, ob ich vorher mod (in diesem Fall mod 29) rechne oder vorher schon. Allerdings ist mir absolut nicht klar, was das rechnen in GF[29] für Auswirkungen auf Brüche und damit auf das Ergebnis dieser Aufgabe hat? Hat da jemand plan? Warscheinlich würde mir eine Seite mir Infos zum praktischen rechnen mit mod bzw. in GF[x] auch erstmal helfen. Ich möchte gerne für Ausdrücken wie: $\begin{eqnarray} \frac{37}{31} mod 29 \end{eqnarray}$ (bzw. in GF[29]) wissen, was ich machen darf und was ich besser lassen sollte. Wäre für Hinweise und Links dankbar.
09.05.2005, 00:19	AD	Auf diesen Beitrag antworten »
Dreh- und Angelpunkt ist das Finden der Inversen zu gegebenen Werten. Das kannst du z.B. über den erweiterten euklidischen Algorithmus http://www.mirsky.de/ggt.php erledigen, oder einfach durch systematisches Probieren, also z.b. 9k für k=0,1,...,28 berechnen und sehen, wo 1 modulo 29 rauskommt. Hier ist das z.B. $\begin{eqnarray} 9\cdot 13=117\equiv 1\mod 29 \end{eqnarray}$ , also gilt in GF[29] die Beziehung $\begin{eqnarray} \frac{1}{9}=13 \end{eqnarray*}$ .
09.05.2005, 08:50	Mantisse	Auf diesen Beitrag antworten »
Hallo Hitchhiker, Also erstens ist mir noch nicht ganz klar, wie ich das Inverse berechne. Ich kenn zwar den Erw. Euklidschen Algor., aber was mache ich damit überhaupt genau? Ich errechne den GGT.. nur warum mache ich das und mit welchen Eingabewerten? Könntest Du das genauer aufschreiben, dann denke ich mal es wird klar werden. Frage ist also: Wie finde ich also das k, welches $\begin{eqnarray} 9k \equiv 1 (mod 29) ; k=0,1,2,..,28 \end{eqnarray}$ erfüllt? Was packe ich wo in ggt(x,y) rein? Darauf folgt, dass mit der Zusammenhang der Inverse mit dem Bruch noch nicht ganz klar geworden ist. Die Inverse ist, soweit ich das verstanden habe ja das Vielfache von einer Zahl (hier 9), welches (hier in GF[29]) kongruent 1 ist. Das hatte ich ja oben schon gefragt, wie du jetzt aber von 9 k = 117 = 1 ( k=13 gilt ja) darauf kommst, dass 1/9 = 13 (mod 29) ist.. ist mir noch nicht ganz klar... kannst du das erläutern? Danke Mantisse
09.05.2005, 09:02	AD	Auf diesen Beitrag antworten »
Der "normale" euklidische Algorithmus berechnet zu zwei Zahlen a und b (hier a=29, b=9) nur den ggT(a,b). Der ist hier gleich Eins, das ist sicher keine Überraschung. Aber der erweiterte euklidische Algorithmus (EEA) liefert zudem Zahlen u,v mit der Eigenschaft ua + vb = ggT(a,b) Und das ist ja genau das, was wir für die Inverse brauchen! Am konkreten Beispiel: Der EEA liefert also Zahlen u,v mit 29u + 9v = 1 , dann folgt unmittelbar 9v = 1 mod 29 und somit ist das erhaltene v die Inverse zu 9. Wenn du das von mir oben bereits verlinkte PHP-Skript http://www.mirsky.de/ggt.php mal mit den Werten a=29 und b=9 aufrufst, dann siehst du in einer der letzten Zeilen unten fettgedruckt die Gleichung 1=-429+139 Erklaerung: y=ua+vb* Du siehst also u=-4 und v=13 kommen als Ergebnis dieses EEA raus. Alles klar?
18.05.2005, 15:36	Mantissen	Auf diesen Beitrag antworten »
Hi Mr Dent! Ich glaube jetz habe ich es kapiert! ich suche mir die multiplikative Inverse von 9 in mod29 mit der EEA. da haben wir eben die 13 raus. jetzt rechnen bzw erweitern wir 1/9 * 13/13 = 13/1 = 13 ... rischtisch? weil wir eben die inverse haben, erreichen wir, dass der nenner 1 wird (genau das wollten wir ja!) darf ich im GF[x] denn generell mit brüchen rumrechnen und erweitern und kürze wie ich will und dann (nach dem vereinfachen) einfach so das entsprechende element \in GF[x] suchen und hinschreiben, oder gibt es da noch etwas zu beachten beim praktischen rechnen mit brüchen im GF[x] ?? danke Mantisse
18.05.2005, 15:48	AD	Auf diesen Beitrag antworten »
Sofern x eine Primzahl ist, gibt es im Bereich der vier Grundrechenarten keine Einschränkungen bis auf die, dass im Nenner natürlich nicht Null (bzw. Vielfache der Primzahl x) stehen darf. Ist x hingegen keine Primzahl, dann ist GF[x] (sofern es für x überhaupt ein solches GF[x] gibt) ja was völlig anderes, also nicht isomorph zum Restklassenring $\begin{eqnarray} \mathbb{Z}_x \end{eqnarray}$ .
Anzeige

18.05.2005, 17:41	Mantisse	Auf diesen Beitrag antworten »
Soll heißen, dass wir es bei $\begin{eqnarray} {Z}_x \end{eqnarray}$ nur mit einem Körper zu tun haben, wenn x Prinzahl ist. Ansonsten ist es nicht mal sicher, dass x ein Körper ist und damit ist das Rechnen natürlich eingeschränkt bzw. manche Operationen würden aus dem Körper $\begin{eqnarray} {Z}_x \end{eqnarray}$ herausführen? Soll also heißen, dass jeder Restklassenring ein Körper $\begin{eqnarray} {Z}_x \end{eqnarray}$ mit x=Primzahl ist. Richtig?
18.05.2005, 17:47	AD	Auf diesen Beitrag antworten »
Deine Formulierung ist etwas unglücklich. $\begin{eqnarray} \mathbb{Z}_x \end{eqnarray}$ existiert ja als Restklassenring auch für Nichtprimzahlen x, nur ist es eben dann kein Körper. Siehe auch http://de.wikipedia.org/wiki/Restklassenring Abschnitt Restklassenkörper.
18.05.2005, 23:00	Mantisse	Auf diesen Beitrag antworten »
Ok. Das klingt gut. Ich habe für alle die es interessiert hier auf Seite 4 ein, wie ich finde, ganz gutes Beispiel für den EEA gefunden. Das multiplik. Inverse steht dort in der y-Spalte in der vorletzten Zeile neben dem ggt(x,y). http://rzwwwneu.fh-wuerzburg.de/fh/fb/al...SCHNELL/RSA.pdf
19.05.2005, 00:06	Mantisse	Auf diesen Beitrag antworten »
Obwohl sich da doch glatt noch bei mir die Frage anschließt, wie ich das folgende in $\begin{eqnarray} {Z}_17 \end{eqnarray}$ bzw. genrell in $\begin{eqnarray} {Z}_x \end{eqnarray}$ am effektivsten brechne? $\begin{eqnarray} \log_{3}{15} = x \end{eqnarray}$ Meine Idee war erstmal mit den Log.gesetzte das ganze in Potenzform zu bringen: $\begin{eqnarray} 3^x = 15 \end{eqnarray}$ Ich kann solche Aufgaben durch probieren lösen, aber das macht ja, grade in einer Klausur, nicht wirklich glücklich. Hat jemand einen Hinweis, wie ich eben jendes Problem fix in Restklassenringen löse?
19.05.2005, 15:25	AD	Auf diesen Beitrag antworten »
Mit Primitivwurzeln kennst du dich hoffentlich aus, wenn du Schreibweisen wie $\begin{eqnarray} \log_b(x) \end{eqnarray}$ imn Restklassenring verwendest, oder?
20.05.2005, 12:57	Mantisse	Auf diesen Beitrag antworten »
ja, ich denke eine primitivwurzel ist ein erzeugendes element eines restklassenrings. erzeugt also alle elemente. ich habe hier jedoch einfach diesen ausdruck als aufgabe bekommen und soll den ausrechnen... gibt es da eine faustregel?
20.05.2005, 13:01	Mantisse	Auf diesen Beitrag antworten »
neben dem log-problem (ich nenne das mal (1)) habe ich noch eine weitere fragen zu dem thema: (2) ist 0 z.b. in $\begin{eqnarray} Z_{26} \end{eqnarray}$ eine Einheit? (Gibt es also eine Inverse zu 0) oder ist 0 einfach per Definition immer Nullteiler?
20.05.2005, 20:54	Mantisse	Auf diesen Beitrag antworten »
Ich ziehe Frage (2) zurück. Keinen Plan was ich mir dabei gedacht hab'. Natürlich ist 0 immer Nullteiler und keine Einheit =)
20.05.2005, 21:07	Mantisse	Auf diesen Beitrag antworten »
Wobei mich dieser Kommenrar hier von LOEF in einem anderen Thread dann wieder stutzig macht: "alle körper sind nullteilerfrei" Dann wäre ja in einem primen Restklassenring auch kein Nullteiler enthalten (es ist ja ein Körper).. Wenn die Aussage oben stimmt, dann wäre 0 auch nicht Nullteiler.
17.09.2006, 11:36	AD	Auf diesen Beitrag antworten »
Geschlossen, da häufig Ziel von Spamattacken. Bei Bedarf PN an einen Moderator, dann wird wieder geöffnet.

Neue Frage »

Antworten »

Interpolation im GF[x]

Verwandte Themen