Berlekamp-Algo. Faktorisierung < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 11:01 Di 18.12.2012 | | Autor: | Pauli85 |
Hallo,
ich möchte mit dem Berlekamp-Algorithmus ein quadratfreies Polynom aus [mm] \IF_{q} [/mm] faktorisieren mit [mm] q=p^n, [/mm] wobei p eine Primzahl ist und n [mm] \in \IN.
[/mm]
Wenn q eine Primzahl ist (also n=1), dann funktioniert das Ganze wunderbar. Allerdings habe ich noch Probleme wenn q keine Primzahl ist.
Ein kleines Beispiel: f(x) = [mm] x^2+x+2 \in \IF_{4}. [/mm] Nun bilde ich zuerst die Basiselemente mit [mm] \beta: [/mm] a [mm] \mapsto a^q [/mm] - a ab. Damit erhalte ich 1 [mm] \mapsto [/mm] 0, x [mm] \mapsto x^4 [/mm] - x [mm] \equiv [/mm] 2x + 2 mod f. Also sieht meine Berlekamp-Matrix wie folgt aus:
B := [mm] \pmat{ 0 & 2 \\ 0 & 2 }. [/mm] Der Kern dieser Matrix ist Kern(B) = {(1,0)}.
Nun das Problem: im Kern liegt nur ein konstantes Polynom, nämlich g(x)=1 [mm] \in \IF_{4}. [/mm] Damit wäre f nach dem Berlekamp-Algorithmus irreduzibel. Aber mit einem Programm erhalte ich diese Faktorisierung von f: f(x)=(x+2)*(x+3). Was stimmt also nicht an meinen Berechnungen? Ich habe dies natürlich auch schon mit anderen Polynomen in anderen Körpern probiert und es hat nie geklappt wenn q keine Primzahl ist.
Wäre über Hilfe sehr dankbar,
Viele Grüße
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:19 Di 18.12.2012 | | Autor: | felixf |
Moin!
> ich möchte mit dem Berlekamp-Algorithmus ein
> quadratfreies Polynom aus [mm]\IF_{q}[/mm] faktorisieren mit [mm]q=p^n,[/mm]
> wobei p eine Primzahl ist und n [mm]\in \IN.[/mm]
> Wenn q eine
> Primzahl ist (also n=1), dann funktioniert das Ganze
> wunderbar. Allerdings habe ich noch Probleme wenn q keine
> Primzahl ist.
> Ein kleines Beispiel: f(x) = [mm]x^2+x+2 \in \IF_{4}.[/mm] Nun
> bilde ich zuerst die Basiselemente mit [mm]\beta:[/mm] a [mm]\mapsto a^q[/mm]
> - a ab. Damit erhalte ich 1 [mm]\mapsto[/mm] 0, x [mm]\mapsto x^4[/mm] - x
> [mm]\equiv[/mm] 2x + 2 mod f. Also sieht meine Berlekamp-Matrix wie
> folgt aus:
> B := [mm]\pmat{ 0 & 2 \\ 0 & 2 }.[/mm] Der Kern dieser Matrix ist
> Kern(B) = {(1,0)}.
Kann es sein, dass du [mm] $\IZ/4\IZ$ [/mm] mit [mm] $\IF_4$ [/mm] verwechselst? In [mm] $\IF_4$ [/mm] ist $2 = 0$, in [mm] $\IZ/4\IZ$ [/mm] nicht.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:20 Fr 21.12.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
