Matroids Matheplanet Forum Index
Forumbereich moderiert von: Buri Gockel
Strukturen und Algebra » Polynome » Euklidischer Algorithmus über Polynomring
Druckversion
Druckversion
Universität/Hochschule J Euklidischer Algorithmus über Polynomring
MePep Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 08.05.2020, Mitteilungen: 167
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Themenstart: 2020-09-17

Hallo!

Ich habe folgende Aufgabe:

"Berechnen sie den ggT von $f = (x^{3}+x^{2}+x)$ und $g = (x^{3}+1)$ im Polynomring $\mathbb{F}_{2}[X]$ und finden Sie eine Darstellung der Form:
ggT(f,g) = $p \cdot f + q \cdot g$"

In unserem Skript steht leider nicht wie man so etwas berechnet, aber ich habe es einfach mal mit der Polynomdivision versucht und wollte wissen ob mein Ergebnis stimmt:

Als ggT(f,g) habe ich $(x^{2}+x+1)$ raus, und damit automatisch die Umstellung $(x^{2} + x + 1) = 1 \cdot (x^{3} + x^{2} + x) - 1 \cdot (x^{3} + 1)$ heraus, also p und q = 1. Könnte das stimmen ?


(Meine Polynomdivision zwischenschritte sehen so aus:
1. $(x^{3}+x^{2}+x) = 1 \cdot (x^{3} + 1) + (x^{2} + x + 1)$
2. $(x^{3} + 1) = (x-1)(x^{2} + x + 1) + 0$

Mfg



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
sonnenschein96 Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 26.04.2020, Mitteilungen: 218
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.1, eingetragen 2020-09-17

Hallo MePep,

das scheint richtig zu sein.

Zu "In unserem Skript steht leider nicht wie man so etwas berechnet":

Allgemein berechnet man einen ggT zweier Elemente eines euklidischen Ringes (Ring in dem man Division mit Rest durchführen kann) mittels des euklidischen Algorithmus.

Möchte man den ggT dann auch wieder als Linearkombination der Elemente ausdrücken, benutzt man den sogenannten erweiterten euklidischen Algorithmus.

Einfach mal googlen :)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
MePep Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 08.05.2020, Mitteilungen: 167
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.2, vom Themenstarter, eingetragen 2020-09-17

2020-09-17 22:12 - sonnenschein96 in Beitrag No. 1 schreibt:
Hallo MePep,

das scheint richtig zu sein.

Zu "In unserem Skript steht leider nicht wie man so etwas berechnet":

Allgemein berechnet man einen ggT zweier Elemente eines euklidischen Ringes (Ring in dem man Division mit Rest durchführen kann) mittels des euklidischen Algorithmus.

Möchte man den ggT dann auch wieder als Linearkombination der Elemente ausdrücken, benutzt man den sogenannten erweiterten euklidischen Algorithmus.

Einfach mal googlen :)

Ok vielen dank!
Ich wusste nur nicht ganz wie ich mit den variablen umgehen soll in $\mathbb{F}_{2}$, aber scheinbar scheint das ja analog zu funktionieren wie man es z.B. aus den reellen Zahlen kennt. X steht hier ja vermutlich auch nur als Platzhalter für Elemente aus dem Ring, also 0 und 1 nehme ich an?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kezer Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 04.10.2013, Mitteilungen: 1039
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.3, eingetragen 2020-09-17

Der euklidische Algorithmus ist ein allgemeines Prinzip, welcher in euklidischen Ringen funktioniert.


-----------------
The difference between the novice and the master is that the master has failed more times than the novice has tried. ~ Koro-Sensei



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
sonnenschein96 Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 26.04.2020, Mitteilungen: 218
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.4, eingetragen 2020-09-17

Du führst die ganz normale Polynomdivision im Ring \(\mathbb{F}_2[X]\) durch. Das geht genauso wie in \(\mathbb{R}[X]\), nur dass die Koeffizienten eben aus \(\mathbb{F}_2\) und nicht aus \(\mathbb{R}\) sind.
Nicht die Variablen sind hier wichtig, sondern die Koeffizienten.

Die Variable X ist hier kein Platzhalter für 0 und 1!
Da sollst Du ja auch nichts einsetzen.

Du muss sauber zwischen Polynom und Polynomfunktion unterscheiden.

Das Polynom \(X^2+X\in\mathbb{F}_2[X]\) ist z.B. nur eine andere Notation für die Folge \((0,1,1,0,0,\ldots)\) und dies ist nicht das Nullpolynom.

Die zugehörige Polynomfunktion \(\mathbb{F}_2\to\mathbb{F}_2,x\mapsto x^2+x\) ist die Nullfunktion, da \(0^2+0=0\) und \(1^2+1=0\).

[Die Antwort wurde vor Beitrag No.1 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
MePep hat die Antworten auf ihre/seine Frage gesehen.
MePep hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]