Forum:  Polynome
Thema: Euklidischer Algorithmus über Polynomring
Themen-Übersicht
MePep
Aktiv
Dabei seit: 08.05.2020
Mitteilungen: 167
Aus:
Themenstart: 2020-09-17 20:35

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


sonnenschein96
Senior
Dabei seit: 26.04.2020
Mitteilungen: 217
Aus:
Beitrag No.1, eingetragen 2020-09-17 22:12

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 :)


MePep
Aktiv
Dabei seit: 08.05.2020
Mitteilungen: 167
Aus:
Beitrag No.2, vom Themenstarter, eingetragen 2020-09-17 22: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?


Kezer
Senior
Dabei seit: 04.10.2013
Mitteilungen: 1037
Aus:
Beitrag No.3, eingetragen 2020-09-17 22:35

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


sonnenschein96
Senior
Dabei seit: 26.04.2020
Mitteilungen: 217
Aus:
Beitrag No.4, eingetragen 2020-09-17 22:40

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.]




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=249459=2004
Druckdatum: 2020-12-02 04:24