Elementare Zahlentheorie

24. June 2011 Mathematik
  • Titel: Elementare Zahlentheorie
  • Organisation: UNI ULM
  • Seitenzahl: 79

Skript herunterladen (PDF)

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