Quadratfreie Faktorisierung von f (X) ∈ Fp [X]
I
E INGABE: f = f1 f22 f33 · · · fkk
I
AUSGABE: Die Liste paarweise teilerfremder Teiler [f1 , . . . , fk ]
von f .
Q
A LGORITHMUS: T1 := ggT(f, f 0 ), V1 := f /T1 = p6 | i fi .
Fur
¨ m ≥ 2 sei Vm := ggT(Vm−1 , Tm−1 ), falls p6 | (m − 1)
und Vm := Vm−1 sonst. Setze Tm := Tm−1 /Vm .
I
I
I
Dann gilt
Vm =
Y
i≥m,p6 | i
fi , Tm =
Y
i>m,p6 | i
fii−m
Y
fii .
p|i
I
Also fm = Vm /Vm+1 fur
¨ alle m mit p6 | m.
Q
Am Ende ist Vk+1 konstant und Tk = p|i fii eine p-te Potenz.
Pn
Pn
Ist Tk = j=0 aj X pj so setze g := j=0 aj X j .
I
Dann ist g p = Tk
I
Wiederhole den Algorithmus mit g anstelle von f solange bis
Tk = 1 ist.
I
I
Faktorisieren in Polynome, deren irreduzible Faktoren
alle den gleichen Grad haben.
d
Sei φd (X) := X p − X ∈ Fp [X]. Dann ist φd (X) das Produkt aller
irreduziblen normierten Polynome in Fp [X] deren Grad d teilt.
I
E INGABE: quadratfreies normiertes Polynom f ∈ Fp [X].
I
AUSGABE
Q : f1 , . . . , fk mit
fd = {q ∈ Fp [X] | q | f, q normiert, irreduzibel vom Grad d}.
I
A LGORITHMUS:
for j from 1 to Grad (f ) do
j
fj := ggT(f, X p − X);
f := f /fj ;
end for;
C ANTOR-Z ASSENHAUS-Algorithmus
I
E INGABE: A ∈ Fp [X] Produkt von mindestens zwei
verschiedenen irreduziblen Polynomen vom Grad d.
I
A
.
AUSGABE: Ein nichttrivialer Faktor B von A = B B
I
A LGORITHMUS: k := Grad(A);
while (TRUE) do
¨
¨
Wahle
zufallig
T ∈ Fp [X] mit Grad(T ) ≤ 2d − 1;
Berechne B := ggT(T (p
d
−1)/2
− 1, A) mit Euklidischen Alg.;
if k > Grad(B) > 0 then RETURN(B); end if;
end while;
Berlekamp Algorithmus
I
I
I
E INGABE: A ∈ Fp [X] quadratfrei, nicht irreduzibel, n := Grad(A).
AUSGABE: nichttriviale Faktorisierung von A.
A LGORITHMUS: Bestimme eine Fp -Basis von M
M := {T ∈ Fp [X] | Grad(T ) < n, T p ≡ T (mod A)}
Pn−1
Pn−1
Ist T (X) = j=0 tj X j ∈ M, so ist T p (X) = T (X p ) = j=0 tj X pj .
Berechne also die Matrix Q = (qji ) ∈ Fn×n
mit
p
X pj ≡
n−1
X
qji X i
(mod A).
i=0
Dann gilt T p ≡ T (mod A) ⇔ (t0 , . . . , tn−1 ) ∈ Kern(Q − In ).
I
I
t ∈ Kern(Q − In ) ↔ T ∈ M mit T ≡ si (mod Ai ).
t l.u. von 1, so si ∈ Fp nicht alle gleich und
Y
A=
ggT(T − s, A)
s∈Fp
ist eine nichttriviale Faktorisierung von A.
f (x) = x30 − x20 + 1 ∈ F3 [x]
I
ggT(f, f 0 ) = 1 also ist f separabel
I
ggT(f, x3 − x) = 1 fur
¨ i = 1, . . . , 5
I
f6 := ggT(f, x3 − x) = x6 + 2x4 + x2 + 1
I
Setze
g := ff6 = x24 + x22 + x18 + x14 + 2x10 + x8 + 2x6 + 2x4 + 2x2 + 1
I
ggT(g, x3 − x) = 1 fur
¨ i = 7, . . . , 11.
I
ggT(g, x3
I
Also g = g1 g2 mit Grad(gi ) = 12.
I
C ANTOR-Z ASSENHAUS: s :=
I
i
6
i
12
− x) = g.
312 −1
2
= 265720
s
T := x + 1, ggT(g, T ) = 1 und
ggT(g, T s +1) = g1 = x12 −x10 +x9 +x8 −x7 −x6 −x5 −x4 +x3 +x+1
I
Setze
g2 := gg1 = x12 − x10 − x9 + x8 + x7 − x6 + x5 − x4 − x3 − x + 1
dann ist f = f6 g1 g2 .
© Copyright 2024 ExpyDoc
