Ferienübung Aufgabe 2

wulf.p
Neuling
Neuling
Beiträge: 10
Registriert: 9. Apr 2011 02:17

Ferienübung Aufgabe 2

Beitrag von wulf.p » 11. Jan 2014 16:01

Hallo,

ich habe eine Frage bezüglich der Aufgabenstellung, bzw. der vorgehensweise bei dieser Aufgabe.
Es ist verlangt eine Lösung für f(x) und g(x) zu finden, sodass p(x) * f(x) + k(x) * g(x) = 1.
Soweit so gut, doch wenn ich das mit dem erweiterten euklidischen Algorithmus lösen möchte, setzt das nicht vorraus, dass ggT(p(x), k(x)) = 1 ist?
Sehe ich das richtig?
Vielen Dank,

Grüße
Wulf

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Ferienübung Aufgabe 2

Beitrag von JannikV » 11. Jan 2014 16:43

Bei mir kam auch nicht 1 raus. Ganz verloren ist man trotzdem nicht.

\(p(x) * f(x) + k(x) * g(x) = c\)

\(\Longleftrightarrow\)
\(p(x) * \dfrac{f(x)}{c} + k(x) * \dfrac{g(x)}{c} = 1\)


VG

wulf.p
Neuling
Neuling
Beiträge: 10
Registriert: 9. Apr 2011 02:17

Re: Ferienübung Aufgabe 2

Beitrag von wulf.p » 11. Jan 2014 17:16

Manchmal sieht man den Wald vor lauter Bäumen nicht mehr... :roll:

Vielen Dank!

Grüße
Wulf

MilesDavis
Erstie
Erstie
Beiträge: 22
Registriert: 7. Feb 2008 11:15

Re: Ferienübung Aufgabe 2

Beitrag von MilesDavis » 14. Jan 2014 15:28

JannikV hat geschrieben:Bei mir kam auch nicht 1 raus. Ganz verloren ist man trotzdem nicht.

\(p(x) * f(x) + k(x) * g(x) = c\)

\(\Longleftrightarrow\)
\(p(x) * \dfrac{f(x)}{c} + k(x) * \dfrac{g(x)}{c} = 1\)


VG
Heißt das jetzt, für den Fall, dass ggT von

\(p(x)\) und \(k(x) \neq 1\)

, dass die gesuchten Polynome

\(\frac{f(x)}{c}\) und \(\frac{g(x)}{c}\)

sind? Sich also aus diesen beiden das Lösungswort berechnet?
Vielen Dank schon mal im Vorraus!

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Ferienübung Aufgabe 2

Beitrag von JannikV » 14. Jan 2014 15:32

Also alles muss man ja nun auch nicht verraten. Bisschen Eigenleistung muss ja noch irgendwo dabei sein ^^
Aber in der Aufgabe steht ja welche Bedingung die gesuchten Polynome erfüllen müssen. Das kann man ja mal nachrechnen und sich dann zufrieden zurücklehnen.... :wink:

MilesDavis
Erstie
Erstie
Beiträge: 22
Registriert: 7. Feb 2008 11:15

Re: Ferienübung Aufgabe 2

Beitrag von MilesDavis » 14. Jan 2014 15:40

JannikV hat geschrieben:Also alles muss man ja nun auch nicht verraten. Bisschen Eigenleistung muss ja noch irgendwo dabei sein ^^
Aber in der Aufgabe steht ja welche Bedingung die gesuchten Polynome erfüllen müssen. Das kann man ja mal nachrechnen und sich dann zufrieden zurücklehnen.... :wink:
Okok... Obwohl es schon ganz schön viel Eigenleistung war, den EEA zu machen. Mein ganzer Schreibtisch ist voll Zettel mit Polynomen! :wink: Wollte ja nur sichergehen, die Aufgabenstellung richtig interpretiert zu haben. Gruß.

Edit: Ok, alles aufgegangen! Dankeschön! :D

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Ferienübung Aufgabe 2

Beitrag von JannikV » 15. Jan 2014 10:23

MilesDavis hat geschrieben:Mein ganzer Schreibtisch ist voll Zettel mit Polynomen!
Aber den Rechenweg müssen wir ja eh mit abgeben, oder?! Anschließend noch die Probe zu machen soll nicht mehr das Problem sein. Da gibts ja Computeralgebrasysteme die das für einen erledigen können. Ich empfehle sage, allerdings ist das für Windows wohl noch nicht so einfach zu installieren. Gibt ja auch noch pari/gp, was der Professor vorgestellt hat, oder andere.

nux
Erstie
Erstie
Beiträge: 12
Registriert: 29. Aug 2012 19:08

Re: Ferienübung Aufgabe 2

Beitrag von nux » 15. Jan 2014 13:08

Wenn ihr sagt, dass bei euch \(p(x) * f(x) + k(x) * g(x) = c\) rauskommt, meint ihr dann, dass \(p(x) * f(x) + k(x) * g(x)\) wirklich \(c\) ergibt (wenn man die Polynome ganz normal multipliziert, addiert und anschließend die Koeffizienten modulo 7 nimmt) oder meint ihr damit, dass das Ergebnis ein Element aus der Restklasse von c modulo p ist?
Ich frage deswegen, weil bei mir c ein Polynom größer p ist und wenn ich c mod p rechne kommt, ganz normal der ggT(f,k) raus. Ich dachte mir zunächst, dass es einfach beabsichtigt sei, dass wir einen Polynom-Restklassenkörper rechnen, aber leider kann ich nichts in der Aufgabenstellung finden, das darauf hindeutet.


Gruß
tobi

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Ferienübung Aufgabe 2

Beitrag von JannikV » 15. Jan 2014 13:45

Ich verstehe die Formulierung leider nicht ganz. Man hat da die Polynome und rechnet diese zusammen. Da es Polynome aus dem Restklassenring sind rechnet man auch immer schön modulo. c ist dabei der ggt. Wenn bei dir c ein Polynom ist und keine Zahl, dann könnte es sein, dass du halt durch dieses Polynom teilen musst. Das kann ich nicht ausschließen, weiß es aber nicht.
Am besten verifizierst du mal Zwischenergebnisse mit nem Computeralgebrasystem.

franzose
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 146
Registriert: 9. Okt 2009 00:08

Re: Ferienübung Aufgabe 2

Beitrag von franzose » 16. Jan 2014 21:36

Da das vorgegebene Polynom irreduzibel ist (wurde von einem Tutor bestätigt), kann soweit ich weiß beim Euklid als ggT kein Polynom herauskommen (bin mir nicht so sicher, also nicht für bare Münze nehmen). Daher dürfte das Ergebnis c kein Polynom sondern nur eine Zahl mod 7 sein, zwar nicht unbedingt 1, aber wie man das ja dann noch umwandelt steht ja oben.

Thorbur
Mausschubser
Mausschubser
Beiträge: 46
Registriert: 28. Sep 2009 16:04

Re: Ferienübung Aufgabe 2

Beitrag von Thorbur » 17. Jan 2014 05:07

Das ganze Problem bei dem ggT mit Polynomen rührt daher, wie der ggT gefiniert ist. Bei Erweiterungskörpern über einer Primzahl (Galois Field - GF) definiert man ihn normalerweise so, dass es die Elemente sind, die sich von keinem anderen Teiler teilen lassen. Wie man anhand der Definition nun schon merkt ist der ggT hier eine Menge von Elementen und keineswegs immer eine eindeutige Zahl. Deshalb kommt es vor, dass beim ggT mit einem irreduziblen Polynom, wie etwa beim Inversen Berechnen, ein Element des Primkörpers (ohne die null), also \(ggT \in \mathbb{F}^*_p\), herauskommt. Bei dem Fall mit dem irreduziblen Körperpolynom ist es in der Tat so, dass der ggT der ganzen Menge \(\mathbb{F}^*_p\) entspricht. Das kann man sich bei Gelegenheit mal überlegen.
Wie JannikV schon dargestellt hat, muss man in diesem Fall einfach mit dem Inversen des erhaltenen Elements multiplizieren und hat dann das gewünschte Ergebnis.

Antworten

Zurück zu „Archiv“