WS 2009/10 Diskrete Strukturen - TUM - Chair VII · Vorlesung Diskrete Strukturen WS 09/10 Prof. Dr. J. Esparza –Institut für Informatik, TU München 21 Kapitel V –Algebra; Körper

Prof. Dr. J. Esparza

Lehrstuhl für Grundlagen derSoftwarezuverlässigkeit und theoretische

InformatikFakultät für Informatik

Technische Universität München

http://www7.in.tum.de/um/courses/ds/ws0910

WS 2009/10

Diskrete Strukturen



Vorlesung Diskrete Strukturen WS 09/10Prof. Dr. J. Esparza – Institut für Informatik, TU München

2

Kapitel V – Algebraische Strukturen • Algebraische Strukturen

– Grundlagen

– Gruppen

– Endliche Körper

• Zahlenkörper

• Polynomkörper


3

Kapitel V – Algebra; Körper• Definition:

Eine Algebra mit zwei zweistelligen

Operatoren und heißt , falls

. ist eine abelsche Gruppe

mit neutralem Element 0 .

. ist ein Monoid mit neutral

Rin

em Element 1

g

R1

R2

R3.

(

A S, ,

S,

S

S, S.

a b c

) ( ) ( )

( ) ( ) (c )

a b a c a,b,c S

b c a b a a a,b,c S


4

Kapitel V – Algebra; Körper• Definition:

Eine Algebra mit zwei zweistelligen

Operatoren und heißt , falls

. ist eine abelsche Gruppe

mit neutralem Element 0 .

. 0 ist eine abelsche

Körper

K1

K Gruppe mit

neutralem

2

A S, ,

S,

S

S \ ,

Element 1

. ( ) ( ) ( )

(Das Rechts-Distributivgesetz folgt aus den

übrigen Eigensch

K

afte

3

n.)

S.

a b c a b a c a,b,c S


5

Kapitel V – Algebra; Körper• Beispiele

(wobei im weiteren Verlauf häufig durch + und ⊙ durch ersetzt werden)

2 2 2

: kommutativer (in Bezug auf ) Ring

1: kommutativer Ring

: Körper

: Körper

n n n

, ,

, , n ,n

, , , , ,

, ,


6

Kapitel V – Algebra; Körper• Beispiel:

Setzt man K = {0,1,a,b} und definiert eine Addition und Multiplikation wie folgt:

so bildet K,⊕,⊙ einen Körper.

0 1 a b

0 0 1 a b

1 1 0 b a

a a b 0 1

b b a 1 0

⊙ 0 1 a b

0 0 0 0 0

1 0 1 a b

a 0 a b 1

b 0 b 1 a


7

Kapitel V – Algebra; Körper• Endliche Körper sind in der Kryptographie und in

der Computer-Algebra sehr nutzlich.• Frage: wie findet man endliche Körper?• Wir werden eine erste Antwort durch diesen Satz

geben:Satz: Bezeichnet man mit +n und n die Addition bzw. Multiplikation Modulo n, so gilt:

ℤn, +n, n ist ein Körper n ist Primzahl.• Zur Vorbereitung brauchen wir einige

Grundeigenschaften des größten gemeinsamen Teilers zweier Zahlen.


8

Kapitel V – Algebra; Körper• Größter gemeinsamer Teiler

Definition:

Seien a, b ℕ. Der größte gemeinsame Teiler von a und b ist die größte natürliche Zahl, die sowohl a als auch b teilt, d.h.

ggT(a, b) := max{k ℕ | k|a und k|b}

wobei k|m eine Abkürzung für „k teilt m“ ist.

Sind a1,…, an ℕ, n 3, dann definieren wir

ggT(a1,…, an) := ggT(ggT(a1,…, an-1), an).


9


Satz: Seien x, y 2 N mit x · y :

1. Wenn y mod x = 0 dann ggT(x,y) = x

2. Wenn y mod x > 0 dann ggT(x,y) = ggT(x,y mod x)

Beweis:

1. Klar. Zu 2. : Es gilt y = (y mod x) + by/xc x. Daraus folgt für alle z 2 N:

(z|x und z|y) gdw. (z|x und z|(y mod x)).

Damit haben (x,y) und (x, y mod x) dieselben gemeinsamen Teiler, und so ggT(x, y) = ggT(x, y mod x).


10


Der Satz führt zum Euklidischen Algorithmus zur Berechnung vom ggT zweier Zahlen:

(Euklid von Alexandria, ca. 325–265 v. Chr.)

Procedure ggT (x, y ℕmit x y)

if y mod x = 0 then return xelse return ggT(y mod x, x)


11


Satz: Seien x, y 2 N. Es gibt a, b 2 Z mit

ggT(x,y) = a x + b y

Beweis: Durch Induktion über max{x,y}.

Basis: max{x,y}=1.

Dann x=1=y und ggT(x,y) = 1 = 1 x + 0 y.

Schritt: max{x,y} > 1.

O.b.d.A. sei x · y. Wir betrachten zwei Fälle.

Fall 1. y mod x = 0. Dann ggT(x,y) = x = 1 x + 0 y.


12


Fall 2. y mod x > 0. In diesem Fall gelten x < y und ggT(x, y) = ggT(y mod x, x). Wir haben

max{y mod x, x} = x < y · max{x,y}

und so (Induktionsannahme) gibt es a´, b´ 2 Z mit

ggT(x,y) = ggT(y mod x, x) = a´ (y mod x) + b´ x

Mit y mod x = y - by/xc x erhalten wir

ggT(x,y) = a´ (y -by/xc x) + b´ x

= (b´-by/xc a´) x + a´ y.


13


Der Beweis des Satzes führt zu einem Algorithmus für die Berechnung der Zahlen a und b, dem Erweiterten Euklidischen Algorithmus:

Procedure ErwggT(Zahlen x,y ℕmit x y)

if y mod x = 0 then return (1, 0)else

(a´, b´) Ã ErwggT(y mod x, x);(a , b) Ã (b´-by/xc a´ , a´);return (a, b)


14


Beispiel mit x= 45, y = 63.

ggT(45,63) 9 = (1 – b63/45c· (-2)) · 45 + (-2) · 63 = = 3 · 45 + (-2) · 63

ggT(18,45) 9 = (0 – b45/18c· 1) · 18 + 1 · 45 = = -2 · 18 + 1 · 45

ggT( 9,18) 9 = 1 · 9 + 0 · 18=9


15

Kapitel V – Algebra; Körper• Eigenschaften von Körpern

Satz: In jedem Körper K gilt für alle a K :

a 0 = 0 a = 0

Beweis:

Es sei a ein beliebiges Element aus K. Dann folgt aus den Axiomen:

0 + (a 0) = a 0 = a (0 + 0) = (a 0) + (a 0).

Die Kürzungsregel ergibt 0 = a 0 □


16


Satz: In jedem Körper K gilt für alle a,b 2 K:

a b = 0 a = 0 oder b = 0.

(Körper sind nullteilerfremd)

Beweis:

Seien a,b mit a b = 0. Falls a 0, so existiert ein multiplikatives Inverses a−1 von a. Unter Verwendung des Satzes auf der letzten Seite folgt damit: b = 1 b = a−1 a b = a−1 0 = 0.


17


Satz: ℤn, +n, n ist ein Körper , n ist Primzahl.

Beweis:

()): Wir beweisen die Kontraposition. Sei n 2 N eine zusammengesetzte Zahl (also keine Primzahl). Dann gibt es Zahlen a,b, mit 1 < a · b < n und a b = n. Insbesondere gilt a 0 b.

Aus a b = n folgt a n b = 0. Damit gilt

a 0 b und a n b = 0. Aus dem Satz auf der vorigen Seite folgt, dass ℤn, +n, n kein Körper ist.


18


Satz: ℤn, +n, n ist ein Körper , n ist Primzahl.

Beweis:

((): Sei n 2 N beliebig. ℤn, +n ist eine abelscheGruppe. Darüber hinaus ist n assoziativ und kommutativ mit neutralem Element 1. Die Distributivgesetze gelten.

Wir zeigen: Wenn n eine Primzahl ist, dann hat jedes Element von ℤn ein inverses Element.


19


Beweis (Forts.):Sei n Primzahl. Zu zeigen ist : für jedes x ℤn gibt es ein y ℤn mit (x n y) 1.Sei x ℤn beliebig. Mit n Primzahl gilt ggT(x,n) = 1. Es existieren also Zahlen a, b 2 Z mit a · x + b · n = 1 (Erweiterter Euklidischer Algorithmus).Damit gilt (a n x) +n (b n n) ´ 1.Aus (b n n) ´ 0 folgt (a n x) ´ 1. Wähle y := a.


20

Kapitel V – Algebraische Strukturen • Algebraische Strukturen

– Grundlagen

– Gruppen

– Endliche Körper:

• Zahlenkörper

• Polynomkörper


21

Kapitel V – Algebra; Körper• Wir untersuchen eine weitere Möglichkeit,

endliche Körper zu konstruieren.

• Die Elemente des Körpers sind nicht mehr Zahlen, sondern Polynome.

• Wir erweitern die Begriffe Summe, Produkt, Division, Rest, Modulo, und Primzahl auf Polynome.

• Wir führen dann einen zweiten Satz über die Existenz endlicher Körper ein.


22

Kapitel V – Algebra; Körper• Definition

Sei hK, +, ¢i ein (kommutativer) Ring. Ein Polynom über K in der Variablen x ist ein Ausdruck der Gestalt.

an ¢ xn + an-1 ¢ xn-1 +…+ a1 ¢ x + a0

wobei n ℕ0, ai K und an 0.

n heißt der Grad des Polynoms, a0,…,an seine Koeffizienten.

K[x] bezeichnet die Menge der Polynome über dem Ring K in der Variablen x.


23

Kapitel V – Algebra; Körper• Definition

Ein Polynom p(x) = an ¢ xn + an-1 ¢ xn-1 +…+ a1 ¢ x + a0

induziert eine Funktion fp : K ! K definiert durch

fp(b) = an ¢ bn + an-1 ¢ bn-1 +…+ a1 ¢ b + a0

für alle b 2 K.

Zwei Polynome sind gleich, wenn sie den gleichen Grad und die gleichen Koeffizienten haben.

(Wir werden später sehen, dass verschiedene Polynome dieselbe Funktion induzieren können.)


24

Kapitel V – Algebra; Körper• Bemerkungen

– In praktischen Anwendungen gilt K = Z oder K = ℤn .

– p(x) = 0 hat Grad 0.

– Formal kann das Polynom

p(x) = anxn + an-1xn-1 +…+ a1x + a0

auch mit der Folge (a0,…,an) gleichgesetzt werden.


25

Kapitel V – Algebra; Körper• Beispiele:

– p(x) = x2 − 2x + 1 ist ein Polynom vom Grad 2.

– Ein linearer Ausdruck p(x)=ax + b mit a 0 ist ein Polynom vom Grad 1.

– Ein konstante Ausdruck p(x) = c ist ein Polynom vom Grad 0.

– Auf ℤ2 ist p(x) = x + x2 ein Polynom mit fp(1) = 1+12 = 0 = fp(0).


26

Kapitel V – Algebra; Körper• Rechnen mit Polynomen

Um den Wert eines Polynoms an einer bestimmten Stelle x0 K zu bestimmen, verwendet man am besten das sogenannte Hornerschema:

11 1 0

1 2 1 0

( )

((...((( ) ) ) )

n nn n

n n n

p x a x a x ... a x a

a x a x a x ... x a x a


27

Kapitel V – Algebra; Körper• Hat man die Koeffizienten in einem Feld a[0..n]

abgespeichert, kann man den Funktionswert p(x0) daher wie folgt berechnen:

begin

p a[n]

for i = n-1 downto 0 do

p p x0 + a[i]

end

end


28

Kapitel V – Algebra; Körper• Die Summe a(x)+b(x) zweier Polynome

a(x) = anxn +…+ a1x + a0 und b(x) = bnxn +…+ b1x + b0

ist definiert durch a(x)+b(x) = cnxn +…+ c1x + c0 , wobei ci = ai + bi.

Die Differenz a(x) -b(x) ist definiert durcha(x)-b(x) = dnxn +…+ d1x + d0 , wobei di = ai + (-bi),und -bi das inverse Element von bi bezüglich der Summe darstellt.

Es gilt: grad(a(x) + b(x)) max{ grad(a(x)) , grad(b(x)) }


29

Kapitel V – Algebra; Körper• Beispiele mit Z als Ring:

– Für a(x) = x2 − 3x + 5 und b(x) = 4x + 2 ergibt sich a(x)+b(x) = x2 + x + 7 und a(x)-b(x) = x2 - 7x +3.

– Für a(x) = x3 + 1 und b(x) = − x3 + 5 ergibt sicha(x)+b(x) = 6 und a(x)-b(x) = 2x3-4.

• Beispiele mit ℤ6 als Ring:– Für a(x) = x2 − 3x + 5 und b(x) = 4x + 2 ergibt sich

a(x)+b(x) = x2 + x + 1 und a(x)-b(x) = x2 + 5x +3

– Für a(x) = x3 + 1 und b(x) = − x3 + 5 ergibt sicha(x)+b(x) = 0 und a(x)-b(x) = 2x3 + 2.


30

Kapitel V – Algebra; Körper• Anmerkungen

– Die Polynomauswertung kann mit O(n = grad(p)) Multiplikationen und Additionen realisiert werden.

– Die Summe (und die Differenz) zweier Polynome vom Grad n lässt sich in O(n) arithmetischen Schritten berechnen.


31

Kapitel V – Algebra; Körper• Das Produkt zweier Polynome

a(x) = anxn +…+ a1x + a0

b(x) = bmxm +…+ b1x + b0

erhält man durch Ausmultiplizieren und anschließendes Sortieren und Zusammenfassen der Koeffizienten, also

20 0 0 1 1 0 0 2 1 1 2 0

0 0

( )( )

m n i

kj i j

i j

a b x a b (a b a b )x (a b a b a b )x ...

a b x .


32

Kapitel V – Algebra; KörperFür den Grad des Produktpolynoms gilt

grad(a · b) = grad(a) + grad(b),

falls K nullteilerfrei ist, ansonsten

grad(a · b) grad(a) + grad(b).


33

Kapitel V – Algebra; Körper• Beispiele:

Für a(x) = x2 − 3x + 5 und b(x) = 4x + 2 ergibt sich

(a b)(x) = (1 4)x3 + (1 2 +(-3) 4)x2 + ((-3) 2 + 5 4)x+ 5 2

= 4x3-10x2 +14x +10.

Das Produkt zweier Polynome vom Grad n lässt sich mit O(n2) arithmetischen Schritten berechnen.


34

Kapitel V – Algebra; Körper• Die Polynomdivision ist analog zur Division mit

Rest bei ganzen Zahlen.

– Auch hier wird fortgesetzt jeweils der höchste Anteil des verbleibenden Polynoms eliminiert.

Für gegebene Polynome a, b mit Koeffizienten aus einem Ring wird hierbei die Gleichung

a(x) = q(x) b(x) + r(x) gelöst,

wobei grad(r) < grad(b) oder grad(r) = 0.


35

Kapitel V – Algebra; Körper• Beispiel

4 3 2 2

4 3 2

3 2

3 2

2

2

2 3 div 1 2 3

(2 2 2 )

2 3

( )

3 3

(3 3 3)

x x x x x x x

x x x

x x x

x x x

x

x x

3 6x


36

Kapitel IV – Algebra; Körper• Für zwei Polynome a und b von Grad höchstens n kann

man die Polynome q und r wie im Beispiel bestimmen.

• Da sich der Grad des Polynoms in jeder Zeile verringert, benötigen wir also höchstens n Multiplikationen von Polynomen mit Konstanten und n Subtraktionen von Polynomen vom Grad höchstens n.

• Insgesamt ergibt sich:

Die Division zweier Polynome vom Grad höchstens nlässt sich mit O(n2) arithmetischen Schritten berechnen.


37

Kapitel V – Algebra; Körper• Satz:

Zu je zwei Polynomen a(x) und b(x), b 0, gibt es eindeutig bestimmte Polynome q(x) und r(x), so dass a(x) = q(x) b(x) + r(x) und r = 0 oder grad(r) < grad(b).

Beispiel:

Im vorhergehenden Schema war das4 3 2 22 3 (2 3) ( 1) ( 3 6)

a(x) q(x) b(x) r(x)

x x x x x x x x


38

Kapitel V – Algebra; Körper• Beweis:

Gilt grad(a) < grad(b), so kann man q = 0 und r = a setzen. Sei also grad(a) grad(b).

Induktion über grad(a):

Basis: grad(a) = 0. Dann folgt aus grad(a) grad(b), dass a und b beides konstante Funktionen sind. Also a(x) = a0 und b(x) = b0 mit b0 0. Wir können daher q(x) = a0/b0 und r(x) = 0 setzen.


39

Kapitel IV – Algebra; Körper• Beweis (Fortsetzung):

Schritt: grad(a) = n > 0. Sei grad(b) = m, m n, und

a(x) = anxn +…+ a1x + a0, an 0

b(x) = bmxm +…+ b1x + b0, bm 0

Wir setzen

c(x) = a(x) − (an/bm)xn−m b(x).

Dann gilt grad(c) < grad(a).

Nach Induktionsannahme gibt es daher Polynome q´(x) und r´(x) mit c(x) = q´(x) · b(x) + r´(x), mit

r´(x) = 0 oder grad(r´) < grad(b).


40


Es gilt

a(x) = (an/bm)xn−m b(x) + q´(x) b(x) + r´(x)

= ((an/bm)xn−m + q´(x)) b(x) + r´(x)

=: q(x) b(x) + r(x) .


41


Um die Eindeutigkeit zu beweisen, nehmen wir an, es gäbe für Polynome a und b zwei Darstellungen wie im Satz angegeben. Also q b + r = a = q´ b + r´ und somit auch(q − q´) b = (r − r´).Wir beweisen q=q´ durch Widerspruch. Falls q q´, ist die linke Seite ein Polynom vom Grad mindestens grad(b). Da die rechte Seite aus der Differenz zweier Polynome vom Grad < grad(b) besteht, ist sie auch ein Polynom mit Grad < b. Widerspruch.

Aus q = q´ folgt r = r´. □


42

Kapitel IV – Algebra; Körper• Polynomringe als Erweiterung der Zahlenringe

hℤ, +i und hℤn, +ni sind abelsche Gruppen.

hℤ[x], +i und hℤn[x], +ni ist eine abelsche Gruppe. Mit + und +n bezeichnen wir hier die Summe von Polynomen.

hℤ, i ist ein abelsches Monoid.

hℤ[x], i ist ein abelsches Monoid. Mit bezeichnen wir hier das Produkt von Polynomen.

hZ, +, ¢i ist ein Ring.

hZ[x],+, ¢i ist ein Ring.


43

Kapitel IV – Algebra; Körper• Polynomringe als Erweiterung der Zahlenringe

hZ, +, ¢i und hZ[x],+, ¢i sind unendliche Ringe.

Um endliche Ringe zu bekommen, haben wir im Zahlen-Fall die Ringe ℤn, +n, n betrachtet.

Die Ringe ℤn[x], +n, n sind jedoch immer noch unendlich, weil ℤn[x] Polynome mit beliebigem Grad enthält.

Z.B. ℤ2[x] = {0, 1, x, x2, x3, x4, … }

Um dieses Problem zu lösen verwenden wir „denselben Trick“ nochmal.


44

Kapitel IV – Algebra; Körper• Wir erweitern die Begriffe Teilbarkeit und

Modulorechnung auf Polynome:

Wir definieren:

– a(x) teilt b(x), wenn es ein Polynom q(x) K[x] gibt, so dass b(x) = q(x) a(x). D.h., der Rest der Polynomdivision ist 0 is.

– a(x) ist kongruent zu b(x) modulo (x),

d.h., a(x) b(x) (mod (x)),

genau dann, wenn a(x) - b(x) durch (x) teilbar ist.


45

Kapitel IV – Algebra; Körper• Beispiel:

Sei K = ℤ3 und ¼(x) = x2+1.

Die möglichen Reste der Division durch ¼(x) sind die Polynome mit Koeffizienten in ℤ3 und Grad 0 oder 1. Es gibt genau 9 davon:

{0, 1, 2, x, x+1, x+2, 2x, 2x+1, 2x+2}

Es gilt z.B. x3+1 (2x+1) mod ¼(x)


46

Kapitel IV – Algebra; Körper• Die Kongruenzrelation teilt die Menge K[x] in

Äquivalenzklassen:

K[x] (x) := {f(x) | f(x) K[x], grad(f) < grad(¼)}.

• Wenn K endlich ist, dann ist K[x] (x) auch endlich.

• Es gilt dann

f(x) + (x) g(x) := (f(x) + g(x)) mod ¼(x)

f(x) (x) g(x) := (f(x) g(x)) mod ¼ (x)


47

Kapitel IV – Algebra; Körper• Wir haben bewiesen

ℤn[x], +n, n ist Körper , n ist Primzahl

• Frage: Wann ist hK[x] (x) , + (x) , (x) i ein Körper?

• Antwort (ohne Beweis):

ℤn[x], +n, n ist Körper , (x) ist irreduzibel

• Definition:

Ein Polynom (x) K[x] mit (x) 0 heißt irreduzibel (über K), falls für alle f(x), g(x) K[x] gilt:

(x) = f(x) g(x) ) grad(f) = 0 oder grad(g) = 0.


48


Betrachten wir K = ℤ2 und (x) = x2+x+1.

ℤ2[x] (x) besteht aus allen Polynomen in ℤ2[x] mit Grad 0 oder 1: ℤ2[x] (x) = {0, 1, x, x+1}

Die Multiplikationstabellen sehen wie folgt aus:

+ (x) 0 1 x x+1

0 0 1 x x+1

1 1 0 x+1 x

x x x+1 0 1

x+1 x+1 x 1 0

(x) 0 1 x x+1

0 0 0 0 0

1 0 1 x x+1

x 0 x x+1 1

x+1 0 x+1 1 x


49


Betrachten wir K = ℤ2 und (x) = x2+1.

ℤ2[x] (x) besteht aus allen Polynomen in ℤ2[x] mit Grad 0 oder 1: ℤ2[x] (x) = {0, 1, x, x+1}

Die Multiplikationstabellen sehen wie folgt aus:

+ (x) 0 1 x x+1

0 0 1 x x+1

1 1 0 x+1 x

x x x+1 0 1

x+1 x+1 x 1 0

(x) 0 1 x x+1

0 0 0 0 0

1 0 1 x x+1

x 0 x 1 x+1

x+1 0 x+1 x+1 0


50

Kapitel IV – Algebra; Körper• Der Grund, warum K = ℤ2 für 1(x) = x2+1 die

Gruppeneigenschaften nicht erfüllt, ist dass

1(x) reduzibel über K ist.

D.h., dass 1(x) als Produkt zweier Polynome vom Grad größer gleich 1 schreiben lässt:

1(x) = x2+1 = (x+1) (x+1) (in ℤ2)

Dies ist für x2+x+1 nicht der Fall.


51

Kapitel IV – Algebra; KörperSatz:

Ist K ein endlicher Körper und (x) ein Polynom in K[x]. Dann gilt:

K[x] (x), + (x), (x) ist ein Körper

(x) ist irreduzibel über K[x].


52

Kapitel IV – Algebra; Körper• Eigenschaften von Restklassenringen

• Satz:

Sei K ein Körper mit n Elementen, und sei g K[x], d = grad(g) 1.

Dann besitzt K[x]g genau nd Elemente.


53

Kapitel IV – Algebra; Körper• Satz:

Zu jeder Primzahl p und zu jeder natürlichen Zahl n 1 gibt es einen endlichen Körper mit pn

Elementen; dieser wird mit GF(pn) bezeichnet

(GF = Galois Field, nach Evariste Galois (1811–1832)).


54

Kapitel IV – Algebra; Körper• Beweis:

n = 1: ℤp = GF(p) ist ein Körper mit p Elementen.

n > 1: Sei K = ℤp. Sei g K[x] ein irreduzibles Polynom vom Grad n.

Dann ist K[x]g ein Körper, und hat genau pn

Elemente (siehe Satz auf Seite 33).

Documents

WS 2009/10 Diskrete Strukturen - TUM - Chair VII · Vorlesung Diskrete Strukturen WS 09/10 Prof. Dr. J. Esparza –Institut für Informatik, TU München 21 Kapitel V –Algebra; Körper