| |
| Autor |
  Euklidischer Algorithmus über Polynomring |
|
MePep
Wenig Aktiv 
Dabei seit: 08.05.2020
Mitteilungen: 167
 |
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
|
 Notiz  Profil
 Quote
 Link |
sonnenschein96
Senior 
Dabei seit: 26.04.2020
Mitteilungen: 493
|      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 :)
|
Notiz Profil
Quote
Link |
MePep
Wenig Aktiv
Dabei seit: 08.05.2020
Mitteilungen: 167
| 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?
|
Notiz Profil
Quote
Link |
Kezer
Senior
Dabei seit: 04.10.2013
Mitteilungen: 1328
 | 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
|
Notiz Profil
Quote
Link |
sonnenschein96
Senior 
Dabei seit: 26.04.2020
Mitteilungen: 493
| 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.]
|
Notiz Profil
Quote
Link |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 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]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
