• Home
  • Mathematics
  • Algebraische und zahlentheoretische Grundlagen für die Informatik: Gruppen, Ringe, Körper, Primzahltests, Verschlüsselung (German Edition)

Algebraische und zahlentheoretische Grundlagen für die Informatik: Gruppen, Ringe, Körper, Primzahltests, Verschlüsselung (German Edition)

Informatikerinnen und Informatiker aller Fachrichtungen müssen die grundlegenden Konzepte, Methoden und Verfahren, die der Entwicklung und dem Einsatz von Informations- und Kommunikationstechnologien zugrunde liegen, verstehen und bei der Lösung von Problemen anwenden können. Das Buch stellt die algebraischen und zahlentheoretischen Grundlagen dafür vor und wendet diese bei der Lösung praktischer Problemstellungen, wie modulare Arithmetik, Primzahltests und Verschlüsselung an. Das Verständnis der Begriffe und deren Zusammenhänge und Zusammenwirken wird u.a. durch Lernziele, integrierte Übungsaufgaben mit Musterlösungen und Marginalien unterstützt. Das Buch ist zum Selbststudium intestine geeignet.

Show description

Quick preview of Algebraische und zahlentheoretische Grundlagen für die Informatik: Gruppen, Ringe, Körper, Primzahltests, Verschlüsselung (German Edition) PDF

Show sample text content

H. die Anzahl der Elemente von Fp [x]/P ! three. nine. three Nullstellen Sei R ein Ring. Falls wir in einem Polynom n P (x) = an x + an−1 x n−1 2 + . . . + a2 x + a1 x + a0 ∈ R[x] die Variable x durch ein point b ∈ R ersetzen, entsteht der time period n P (b) = an b + an−1 b n−1 2 + . . . + a2 b + a1 b + a0 dessen Wert ein aspect von R ist. Es gilt der Satz three. 19 Sei okay ein K¨orper, b ∈ okay und P ∈ K[x]. Dann gilt a) P (b) = c genau dann, wenn ein Polynom Q ∈ K[x] existiert mit P (x) = (x − b) · Q(x) + c, 100 Teilbarkeit von Polynomen b) P (b) = zero genau dann, wenn (x − b)|P (x) ist.

2 (5) ist (w¨ahle a = 1) 2 k−3 five k−1 =1+2 ok (5. nine) = 1 (2 ) ¨ Wir quadrieren und erhalten wieder mithilfe von Ubung 1. 2 (4) und, weil okay ≥ three vorausgesetzt ist: 2 2 k−3 2 five k−2 =5 2k−2 okay okay =1+2 +2 = 1 (2 ) (5. 10) Aus (5. nine) und (5. 10) folgt die Behauptung. ✷ b) folgt unmittelbar aus a). Lemma five. three F¨ur alle n ∈ N0 gilt n+1 a) 4|5 −5 , n n b) five = 1 (4). Beweis a) Es gilt five Behauptung folgt. − five = five · (5 − 1) = five · four, woraus unmittelbar die b) Mit Korollar 1. five gilt n five = 1 (4) folgt.

P − 1 l¨asst sich im p-adischen Zahlensystem mit den Ziffern zero, 1, . . . , p − 1 eindeutig darstellen in der shape a = a0 + a1 p + . . . + aα−1 p α−1 (3. 19) mit ai ∈ {0, 1, . . . , p − 1}, zero ≤ i ≤ α − 1. Es gilt (p , a) = 1 genau dann, wenn α a0 = zero ist. Die Anzahl der Zahlen a in 1, 2, . . . , p − 1 mit der Darstellung ¨ (3. 19) mit a0 = zero ergibt sich durch kombinatorische Uberlegung: F¨ur den Koeffizienten a0 gibt es p − 1 M¨oglichkeiten und f¨ur die α − 1 Koeffizienten ai , 1 ≤ i ≤ α − 1, gibt es jeweils p Ziffern in einem p-adischen Zahlensystem, d.

X − a s−1 x = a oder . . . oder x = a . s s−1 ) ) = zero folgt x = 1 oder l e) Genau die Potenzen a mit (s, l) = 1 besitzen die Ordnung s, und die Anzahl dieser Potenzen betr¨agt ϕ(s). ✷ Satz four. 6 Es sei okay ein endlicher K¨orper mit ordK∗ = q − 1, dann gilt: a) Zu jedem Teiler s von q − 1 gibt es genau ϕ(s) Elemente der Ordnung s, ∗ b) okay besitzt ϕ(q − 1) erzeugende Elemente. a) Aus Korollar three. nine wissen wir, dass f¨ur alle m ∈ N gilt: ϕ(d) = m. F¨ur m = q − 1 und d = s gilt additionally s|(q−1) ϕ(s) = q − 1.

Beweis Wir setzen aus schreibtechnischen Gr¨unden r = ordG (a) s = ordG (b) ok = [ r, s ] = (r, s) (2. eight) (2. nine) okay okay a) Aus (2. eight) folgt r|k und s|k und daraus mit Satz 2. 2 b) a = e und b = e. Hieraus und mit der Voraussetzung, dass a und b kommutieren, folgt ok ok ok e = a ∗ b = (a ∗ b) und daraus wiederum mit Satz 2. 2 b) ordG (a ∗ b)|k, was once zu zeigen struggle. b) ⇒“: Es gilt mit Satz 1. sixteen: ordG (a ∗ b) = r · s = (r, s) · [ r, s ]. Hieraus folgt, ” da wegen a) r · s|[ r, s ] ist, (r, s) = 1 und damit die Behauptung.

Download PDF sample

Rated 4.54 of 5 – based on 44 votes