{VERSION 6 0 "IBM INTEL NT" "6.0" }
{USTYLETAB {CSTYLE "Maple Input" -1 0 "MS Sans Serif" 1 8 128 0 128 1 
0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 
0 0 0 0 0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 }{CSTYLE "Roter Text" -1 256 "Tahoma" 0 0 255 0 0 1 2 1 1 0 0 2 
0 0 0 0 }{CSTYLE "" -1 257 "" 1 12 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }
{CSTYLE "" -1 258 "" 1 12 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 
259 "" 1 12 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 1 12 0 
0 0 0 0 0 1 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "T
imes" 1 10 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }
{PSTYLE "R3 Font 0" -1 256 1 {CSTYLE "" -1 -1 "Helvetica" 1 9 128 0 
128 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "R3 Fo
nt 2" -1 257 1 {CSTYLE "" -1 -1 "Courier" 1 8 0 128 128 1 1 2 2 2 2 2 
1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Seitenumbruch" -1 258 
1 {CSTYLE "" -1 -1 "Times" 1 10 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 
0 0 1 0 1 0 1 2 0 1 }{PSTYLE "Normal" -1 259 1 {CSTYLE "" -1 -1 "Times
" 1 12 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }3 1 0 0 0 0 1 0 1 0 2 2 0 1 }
{PSTYLE "Heading 1" -1 260 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 2 
1 2 2 2 2 1 1 1 1 }1 1 0 0 8 4 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 3" 
-1 261 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 1 1 2 2 2 2 1 1 1 1 }1 
1 0 0 0 0 1 0 1 0 2 2 0 1 }}
{SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 23 "Berlekamp_klein_p.mws  " }
}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 113 "Ein paar Proberechnungen zur Illustratio
n des Berlekampverfahrens (small p), so wie es in \247 16 dargestellt \+
wurde:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "restart:   with(linalg)
:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "#p:=   ;" }}{PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 8 "#d:=   ;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "
#f:=randpoly(x,degree=d) mod p:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "
#f:=(lcoeff(f,x)&^(-1) *f) mod p;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 
0 "" }}{PARA 0 "" 0 "" {TEXT 257 12 "Beispiel (a)" }{TEXT -1 6 " mit  \+
" }{XPPEDIT 18 0 "p = 2;" "6#/%\"pG\"\"#" }{TEXT -1 8 "   und  " }
{XPPEDIT 18 0 "f = x^9+x^4+x^3+1;" "6#/%\"fG,**$%\"xG\"\"*\"\"\"*$F'\"
\"%F)*$F'\"\"$F)F)F)" }{TEXT -1 6 "  :   " }}{PARA 0 "" 0 "" {TEXT -1 
0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 
24 "p:=2:f := x^9+x^4+x^3+1:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "d:=
degree(f,x):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 27 "Als erstes ist di
e Matrix  " }{XPPEDIT 18 0 "L;" "6#%\"LG" }{TEXT -1 28 "  und ihr Kern
 zu bestimmen:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 88 "for k from 0 to d
-1 do R:=Rem(x^(p*k),f,x) mod p; Z||k:=[seq(coeff(R,x,k),k=0..d-1)]:od
:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 76 "L:=map(modp,evalm(concat(seq(Z
||k,k=0..d-1))- array(1..d,1..d,identity)),p);" }}}{EXCHG {PARA 0 "" 
0 "" {TEXT -1 25 "Eine Basis des Kerns ist:" }}{PARA 0 "> " 0 "" 
{MPLTEXT 1 0 22 "G:=Nullspace(L) mod p;" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 28 "Sie besteht aus s Elementen:" }}{PARA 0 "> " 0 "" 
{MPLTEXT 1 0 11 "s:=nops(G);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 77 "D
ie zu den Basisvektoren geh\366renden nichtkonstanten L\366sungen der \+
Kongruenz   " }{XPPEDIT 18 0 "g^p = `mod`(g,f);" "6#/)%\"gG%\"pG-%$mod
G6$F%%\"fG" }{TEXT -1 8 "   sind:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 
52 "for k to s do gg||k:=add(x^(l-1)*G[k][l],l=1..d);od:" }}{PARA 0 ">
 " 0 "" {MPLTEXT 1 0 91 "g:=map(sort,convert(\{seq(gg||k,k=1..s)\} min
us \{1\},list),x): \{seq(`   g`[k]=g[k],k=1..s-1)\};" }}}{EXCHG {PARA 
0 "" 0 "" {TEXT -1 55 "Die komplette Tabelle der in Frage kommenden gg
T-s ist:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 169 "stackmatrix([`    `,se
q('r'=k,k=0..p-1)],concat([seq(`ggT mit   g`[k]* `-r   : `,k=1..s-1)],
map(sort,stackmatrix(seq([seq(Gcd(f,g[k]-r) mod p,r=0..p-1)],k=1..s-1)
),x)));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 53 "Zum Vergleich : Maple \+
liefert die folgende Zerlegung:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "
'f'=Factor(f) mod p;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 124 "Jetzt mu
ss man sich noch was einfallen lassen zur weiteren geschickten Auswert
ung der ggT-s, vgl. Hinweise in der Vorlesung." }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 258 12 "Beisp
iel (b)" }{TEXT -1 6 " mit  " }{XPPEDIT 18 0 "p = 7;" "6#/%\"pG\"\"(" 
}{TEXT -1 8 "   und  " }{XPPEDIT 18 0 "f = x^10+x^9+5*x^7+2*x^4+x+4" "
6#/%\"fG,.*$%\"xG\"#5\"\"\"*$F'\"\"*F)*&\"\"&F)*$F'\"\"(F)F)*&\"\"#F)*
$F'\"\"%F)F)F'F)F3F)" }{TEXT -1 6 "  :   " }}{PARA 0 "" 0 "" {TEXT -1 
0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 
35 "p:=7:f := x^10+x^9+5*x^7+2*x^4+x+4:" }}{PARA 0 "> " 0 "" {MPLTEXT 
1 0 15 "d:=degree(f,x):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 27 "Als er
stes ist die Matrix  " }{XPPEDIT 18 0 "L;" "6#%\"LG" }{TEXT -1 28 "  u
nd ihr Kern zu bestimmen:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 88 "for k \+
from 0 to d-1 do R:=Rem(x^(p*k),f,x) mod p; Z||k:=[seq(coeff(R,x,k),k=
0..d-1)]:od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 76 "L:=map(modp,evalm(c
oncat(seq(Z||k,k=0..d-1))- array(1..d,1..d,identity)),p);" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 25 "Eine Basis des Kerns ist:" }}{PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 22 "G:=Nullspace(L) mod p;" }}}{EXCHG {PARA 0 "" 
0 "" {TEXT -1 28 "Sie besteht aus s Elementen:" }}{PARA 0 "> " 0 "" 
{MPLTEXT 1 0 11 "s:=nops(G);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 77 "D
ie zu den Basisvektoren geh\366renden nichtkonstanten L\366sungen der \+
Kongruenz   " }{XPPEDIT 18 0 "g^p = `mod`(g,f);" "6#/)%\"gG%\"pG-%$mod
G6$F%%\"fG" }{TEXT -1 8 "   sind:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 
52 "for k to s do gg||k:=add(x^(l-1)*G[k][l],l=1..d);od:" }}{PARA 0 ">
 " 0 "" {MPLTEXT 1 0 91 "g:=map(sort,convert(\{seq(gg||k,k=1..s)\} min
us \{1\},list),x): \{seq(`   g`[k]=g[k],k=1..s-1)\};" }}}{EXCHG {PARA 
0 "" 0 "" {TEXT -1 55 "Die komplette Tabelle der in Frage kommenden gg
T-s ist:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 169 "stackmatrix([`    `,se
q('r'=k,k=0..p-1)],concat([seq(`ggT mit   g`[k]* `-r   : `,k=1..s-1)],
map(sort,stackmatrix(seq([seq(Gcd(f,g[k]-r) mod p,r=0..p-1)],k=1..s-1)
),x)));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 53 "Zum Vergleich : Maple \+
liefert die folgende Zerlegung:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "
'f'=Factor(f) mod p;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}
}{EXCHG {PARA 0 "" 0 "" {TEXT 259 10 "Bemerkung:" }{TEXT -1 3 "   " }}
{PARA 0 "" 0 "" {TEXT -1 26 "In beiden Beispielen ist  " }{XPPEDIT 18 
0 "f;" "6#%\"fG" }{TEXT -1 242 "  nicht quadratfrei !  Das ist zur Ill
ustration der Theorie zwar hilfreich, sollte aber bei konkreten Rechnu
ngen vermieden werden. Letzteres ist leicht und schnell m\366glich mit
 Hilfe von einigen ggT-Berechnungen. Siehe z.B. \334bungsaufgabe (49).
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "
" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 260 12 "Beispiel (c)" }{TEXT -1 6 " \+
mit  " }{XPPEDIT 18 0 "p = 5;" "6#/%\"pG\"\"&" }{TEXT -1 8 "   und  " 
}{XPPEDIT 18 0 "f = x^7+3*x^6+x^4+4*x^2+2*x+1;" "6#/%\"fG,.*$%\"xG\"\"
(\"\"\"*&\"\"$F)*$F'\"\"'F)F)*$F'\"\"%F)*&F/F)*$F'\"\"#F)F)*&F2F)F'F)F
)F)F)" }{TEXT -1 6 "  :   " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 
"" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "p:=5:f := e
xpand((x^2+x+1)^2*(x^3+x^2+1)) mod p;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 
0 15 "d:=degree(f,x):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "Fa
ctor(f) mod p;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 67 "Mal sehen, wie \+
wir mit Berlekamp zu einer Zerlegung kommen k\366nnen. " }}{PARA 0 "" 
0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 32 "Als erstes  \374berp
r\374fen wir, ob  " }{XPPEDIT 18 0 "f;" "6#%\"fG" }{TEXT -1 18 "  quad
ratfrei ist:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "diff(f,x) m
od p;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "Factor(%) mod p;" }}{PARA 
0 "> " 0 "" {MPLTEXT 1 0 33 "gf:=Gcd(f,diff(f,x) mod p) mod p;" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 1 " " }{XPPEDIT 18 0 "f;" "6#%\"fG" }
{TEXT -1 49 "  ist also nicht qudratfrei. Daher ersetzen wir  " }
{XPPEDIT 18 0 "f;" "6#%\"fG" }{TEXT -1 8 "  durch:" }}}{EXCHG {PARA 0 
"> " 0 "" {MPLTEXT 1 0 24 "f:=simplify(f/gf mod p);" }}}{EXCHG {PARA 
0 "" 0 "" {TEXT -1 27 "Als erstes ist die Matrix  " }{XPPEDIT 18 0 "L;
" "6#%\"LG" }{TEXT -1 28 "  und ihr Kern zu bestimmen:" }}{PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 88 "for k from 0 to d-1 do R:=Rem(x^(p*k),f,x) mod
 p; Z||k:=[seq(coeff(R,x,k),k=0..d-1)]:od:" }}{PARA 0 "> " 0 "" 
{MPLTEXT 1 0 76 "L:=map(modp,evalm(concat(seq(Z||k,k=0..d-1))- array(1
..d,1..d,identity)),p);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 25 "Eine B
asis des Kerns ist:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "G:=Nullspace
(L) mod p;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 28 "Sie besteht aus s E
lementen:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "s:=nops(G);" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 77 "Die zu den Basisvektoren geh\366re
nden nichtkonstanten L\366sungen der Kongruenz   " }{XPPEDIT 18 0 "g^p
 = `mod`(g,f);" "6#/)%\"gG%\"pG-%$modG6$F%%\"fG" }{TEXT -1 8 "   sind:
" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "for k to s do gg||k:=add(x^(l-1
)*G[k][l],l=1..d);od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 91 "g:=map(sor
t,convert(\{seq(gg||k,k=1..s)\} minus \{1\},list),x): \{seq(`   g`[k]=
g[k],k=1..s-1)\};" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 55 "Die komplett
e Tabelle der in Frage kommenden ggT-s ist:" }}{PARA 0 "> " 0 "" 
{MPLTEXT 1 0 169 "stackmatrix([`    `,seq('r'=k,k=0..p-1)],concat([seq
(`ggT mit   g`[k]* `-r   : `,k=1..s-1)],map(sort,stackmatrix(seq([seq(
Gcd(f,g[k]-r) mod p,r=0..p-1)],k=1..s-1)),x)));" }}}{EXCHG {PARA 0 "" 
0 "" {TEXT -1 53 "Zum Vergleich : Maple liefert die folgende Zerlegung
:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "'f'=Factor(f) mod p;" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "0 3 0" 113 }
{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }