Fakultät für Mathematik 22. Januar 1998 Universität Regensburg

Übungen zur Vorlesung “Angewandte kommutative Algebra”

Tutorium 13: Optimierung des Berlekamp-Algorithmus

In diesem Tutorium sei p eine Primzahl und K = 𝔽_{p}. Unser Ziel ist es, den Berlekamp-Algorithmus zur Berechnung der Primfaktorzerlegung eines normierten Polynoms f ∈ K[X] vom Grad d > 0 zu optimieren.

a) Schreiben Sie eine CoCoA-Funktion Sqfr(F), die den quadratfreien Teil eines Polynoms F ∈ K[X]\{0} nach dem in Satz 13.14 beschriebenen Algorithmus berechnet. Damit können wir uns im Berlekamp-Algorithmus von vorneherein auf den quadratfreien Fall zurückziehen.

b) Sei f = a_{0} + a_{1}X + ⋯ + a_{d−1}X^{d−1} mit a_{0}, …, a_{d−1} ∈ K, und für jedes k ≥ 0 sei NF_{{f}}(X^{k}) = b_{k 0} + b_{k 1}X + ⋯ + b_{k d−1}X^{d−1} mit b_{k i} ∈ K. Zeigen Sie, daß die Koeffizienten b_{k i} der Rekursion b_{k+1 i} = b_{k i−1} − b_{k d−1}a_{i} genügen, und folgern Sie einen schnellen Algorithmus zur Berechnung von NF_{{f}}(X^{p}) für “kleine” Primzahlen p.

c) Entwickeln Sie ein zu b) analoges Verfahren zur Berechnung von NF_{{f}}(X^{pi}) für i > 1, wenn NF_{{f}}(X^{p}) = q_{2 1} + q_{2 2}X + ⋯ + q_{2 d}X^{d−1} gegeben ist. Implementieren Sie die Verfahren aus b) und c), indem Sie ein CoCoA-Programm QMat(F) schreiben, das die in Lemma 13.18 definierte Matrix Q berechnet. Hinweis: Hierbei gilt (q_{1 1}, …, q_{1 d}) = (1, 0, …, 0).

d) Erklären Sie, wie man den Syz-Befehl von CoCoA zur Berechnung einer Basis des Raums aller Vektoren (γ_{0}, …, γ_{d−1}) ∈ K^{d} mit (γ_{0}, …, γ_{d−1})(Q − E_{d}) = 0 verwenden kann.

e) Schreiben Sie eine CoCoA-Funktion SimulGCD(F, G), die die Liste [H_{0}, …, H_{p−1}] aller größten gemeinsamen Teiler H_{i} = ggT(F, G−i) simultan berechnet, indem sie eine neue Variable Y einführt und ggT(F, G − Y) ∈ (K[Y])[X] bestimmt. Hinweis: Nehmen Sie dazu an, daß der Grundring R ::= ℤ/(p)[x, y], Weights(1, 0); ist.

f) Implementieren Sie den Berlekamp-Algorithmus aus Satz 13.20 im Fall K = 𝔽_{p}. Schreiben Sie dazu ein CoCoA-Programm Berlekamp(F), das die in a)-e) beschriebenen Optimierungen verwendet.

g) Zerlegen Sie mit Hilfe von Berlekamp(F) die folgenden Polynome in Primfaktoren:

1) F_{1} = X^{100} − X^{200} ∈ 𝔽_{5}[X]
2) F_{2} = 1 + X + X^{2} + X^{6} + X^{7} + X^{8} + X^{12} ∈ 𝔽_{2}[X]
3) F_{3} = 1 − X^{100} ∈ 𝔽_{7}[X]
4) F_{4} = 8 + 2X + 8X^{2} + 10X^{3} + 10X^{4} + X^{6} + X^{8} ∈ 𝔽_{13}[X]
5) F_{5} = 2 + X + X^{2} + X^{3} + X^{4} + X^{5} ∈ 𝔽_{31991}[X]