
- Titel: Elementare Zahlentheorie
- Organisation: UNI ULM
- Seitenzahl: 79
Inhalt
- Elementare Zahlentheorie Vorlesungsskript
- Prof Dr Irene I Bouw Sommersemester
- diskrete Logarithmus Primitivwurzeln Der diskrete Logarithmus Das ElGamalKryptoverfahren
- Teilbarkeit und der euklidische Algorithmus
- Also ist ggTa b
- Der Fundamentalsatz der Arithmetik
- u pmp nat rliche Zahlen
- pminnp mp und kgVa b
- pminnp mp maxnp mp ggTa b kgVa b
- n ak ak a a a
- i ai a a k ak
- die alternierende Quersumme Allgemeiner nennen wir Qs n
- i aiss ais ais
- Beweis Es gilt aj j
- aiss ais ais is
- Der kleine Satz von Fermat
- Schritt Nun berechnen wir b
- Schritt Wir bemerken dass
- Der chinesische Restsatz
- F r i j gilt u Mj
- da mi m Also schließen wir dass
- x M j M j aj aj
- Mj Mj aj mod m
- i n pi i pi n
- mit t ungerade
- xi xj x x Abbildung Das PollardVerfahren
- Algorithmus Die PollardMethode zweite Version n beliebig
- o Endliche Krper
- ai xi ai K
- Endliche Krper o
- ai ei ai Fp
- Also besitzt k genau pn Elementen
- Der diskrete Logarithmus
- Außerdem gilt dass
- Beispiel Wir lsen die Kongruenz o x mod
- berechnen und damit den Geheimtext entschl sseln u
- Das quadratische Reziprozittsgesetz a
- Die Teilen b und c sind klar
- Beweis Lemma b impliziert dass p p
- Der Beweis des quadratischen Reziprozittsgesetz a
- u us v vt
- falls p falls p
- ja vi uj ps p j j
- Aus folgt dass
- Aus und folgt nun dass
- G ist Also folgt dass
- T p q T q p G G
- Das quadratische Reziprozittsgesetz folgt daher aus a
- Wir schließen dass
- n c m m mn n
- p p r
- Wir schließen dass n
- Teil b folgt hnlich wie a aus a
- pi Satz b und Theorem
- p pr Aq qt B
- Pythagorische Tripel a
- gilt r s mod
- Da y rs nden wir
- Welche Zahlen sind die Summe von zwei Quadraten
- Mit Hilfe von schreiben wir nun
- Die gaußsche Zahlen
- i i i i i i
Vorschau
Elementare ahlentheorie, Vorlesungsskript
Prof. Dr. Irene I. Bouw Sommersemester 2008
Inhaltsverzeichnis
1 Primzahlen 1.1 Teilbarkeit und der euklidische Algorithmus . . . . . . . . . . . . 1.2 Der Fundamentalsatz der Arithmetik . . . . . . . . . . . . . . . . 1.3 Probedivision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Kongruenzen 2.1 Kongruenzen . . . . . . . . 2.2 Der Kalenderformel . . . . . 2.3 Pr¨ fziffer . . . . . . . . . . u 2.4 Teilbarkeitskriterien . . . . 2.5 Der kleine Satz von Fermat 2.6 Schnelle Exponentiation . . 2.7 Der chinesische Restsatz . . 3 Kryptographie 3.1 Die Caesar-Chiffre . . 3.2 Das RSA-Verfahren . . 3.3 Primzahltests . . . . . 3.4 Die Pollard-ρ-Methode 4 Endliche K¨rper o 4.1 K¨rper . . . . . . . . o 4.2 Polynome . . . . . . 4.3 Polynomkongruenzen 4.4 Endliche K¨rper . . o 5 Der 5.1 5.2 5.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 7 10 12 12 15 18 19 21 23 25 28 28 30 33 38 40 40 42 46 48
diskrete Logarithmus 51 Primitivwurzeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 Der diskrete Logarithmus . . . . . . . . . . . . . . . . . . . . . . 54 Das ElGamal-Kryptoverfahren . . . . . . . . . . . . . . . . . . . 56
1
6 Das 6.1 6.2 6.3
quadratische Reziprozit¨tsgesetz a 57 Das Legendre-Symbol . . . . . . . . . . . . . . . . . . . . . . . . 57 Der Beweis des quadratischen Reziprozit¨tsgesetz . . . . . . . . . 59 a Das Jacobi-Symbol . . . . . . . . . . . . . . . . . . . . . . . . . . 63
7 Diophantische Gleichungen 65 7.1 Pythagor¨ische Tripel . . . . . . . . . . . . . . . . . . . . . . . . 66 a 7.2 Welche ahlen sind die Summe von zwei Quadraten? . . . . . . . 69 7.3 Die gaußsche ahlen . . . . . . . . . . . . . . . . . . . . . . . . . 73
Einleitung
Dies ist ein Skript f¨ r der Vorlesung Elementare ahlentheorie. Dies ist ein Voru lesung f¨ r Lehr¨mtler und Bachelorstudenten Mathematik an der Universit¨t u a a Ulm. Ich danke Dr. Robert Carls, Dominik Ufer und Studenten der Vorlesung im SS 2008 und SS 2009 f¨ r das sorgfaltige Lesen des Manuskripts. u
1
1.1
Primzahlen
Teilbarkeit und der euklidische Algorithmus
Wir schreiben N = {1, 2, 3, 4, 5, . . .} f¨ r die Menge der nat¨ rlichen ahlen und u u = {· · · , −2, −1, 0, 1, 2, · · · } f¨ r die Menge der ganzen ahlen. Mit Q bezeichu nen wir die Menge der rationalen ahlen (“Bruchzahlen”). Definition 1.1.1 Seien a = 0 und b ganze ahlen. Wir sagen, dass b durch a teilbar ist, falls es eine ganze ahl c gibt so, dass b = a · c. In diesem Fall heißt a ein Teiler von b. Falls b durch a teilbar ist, so schreiben wir a | b. Falls b nicht durch a teilbar ist, so schreiben wir a ∤ b. Beispiel 1.1.2 Die Teiler von 12 sind ±1, ±2, ±3, ±4, ±6 und ±12. Wir brauchen zuerst einige einfache Eigenschaften der Teilbarkeit. Lemma 1.1.3 Seien a, b, c, m, n ganze ahlen. (a) Falls a | b und b | c, so gilt a | c. (b) Falls c | a und c | b, so gilt c | (ma + nb). Beweis: (a) Es existieren ganze ahlen e und f mit ae = b und bf = c. Also gilt c = bf = aef . Wir schließen daraus, dass c durch a teilbar ist. (b) Es existieren ganze ahlen e und f mit a = ce und b = cf . Daher gilt ma + nb = mce + ncf = c(me + nf ). Also ist ma + nb durch c teilbar. 2 Definition 1.1.4 Seien a, b ganze ahlen (nicht beide 0). Der gr¨ßte gemeino same Teiler von a und b ist die gr¨ßte ahl die sowohl a also auch b teilt. Wir o schreiben daf¨ r: ggT(a, b). Falls ggT(a, b) = 1, so heißen a und b teilerfremd. u Falls a = 0, so ist ggT(a, 0) = a. F¨ r a = b = 0 ist ggT(a, b) nicht definiert. u wei Beispiele sind ggT(16, 12) = 4 und ggT(120, 225) = 15. Dies kann man zum Beispiel nachrechnen, indem man die ahlen faktorisiert: 120 = 23 ·3·5 und 225 = 32 · 52 . F¨ r gr¨ßere ahlen ist dies allerdings nicht praktikabel. Versuchen u o Sie zum Beispiel ggT(1160718174, 316258250) mit Hilfe eines Taschenrechners zu berechnen. Den gr¨ßten gemeinsamen Teiler berechnet man in Maple mit o dem Kommando igcd. Ein sehr effizienter Algorithmus zum Berechnen des ggTs, ist der euklidische Algorithmus. Dieser Algorithmus basiert auf Division mit Rest. 3