TU Chemnitz, Fakultät für Mathematik: Fakultät für Mathematik: Algorithmische und Diskrete Mathematik: Zahlentheorie
ZahlentheorieSommersemester 2013 (F.Göring)
|
 |
Kurzbeschreibung
| Inhalt: | Teilbarkeit, Zahlentheoretische Funktionen, Lineare Kongruenzen, Restklassenringe, Kongruenzrechnung mit Polynomen, Quadratische Reste, Diophantische Gleichungen, reell analytische Methoden in der Zahlentheorie, Verschlüsselung |
| Modulnr: | FD2, FA2 |
| Vorwissen: | Algebra |
| Abschluss: | Schein mit/ohne Note oder Teil einer Fachprüfung |
Übungsaufgaben
Literatur
- M.Aigner, G.M.Ziegler: Proofs from THE BOOK, second edition, Springer 1999 (Chapter 1-6).
- G.H.Hardy, E.M.Wright: An Introduction to the Theory of Numbers, fifth edition, Oxford Press 1980.
Links
- B.H.Matzat, Elementare Zahlentheorie (Skript: A.Christian, Heidelberg, 1992)
- K.Mathiak, Einführung in die Zahlentheorie (Braunschweig, 1993)
- K.Pommerening, Kryptologie Kapitel III. Asymmetrische Verschlüsselung
- A.Winterhof, Pseudozufallszahlen (Skript, Linz, 2005)
Prüfung / Scheingespräch
Es werden die wesentlichen Inhalte der Vorlesung und Übung besprochen. Dabei kommt es insbesondere auf das Verständnis der enthaltenen Ideen an. Auch Algorithmen müssen nicht auswendig gelernt werden. Ihr zu Grunde liegendes Prinzip sollte aber klar sein, sodass sie grob reproduziert werden können.
Schwerpunkte sind:
- Begriffe der Algebra (Gruppe, Ring, Körper, Hauptidealring,...)
- Erweiterter Euklidischer Agorithmus (Satz 1.21) mit Abschätzung der Faktoren
- Satz über die Eindeutigkeit der Primfaktorzerlegung (1.26)
- Primzahltest von Wilson (Satz 1.39)
- Chinesischer Restsatz
- Satz 1.49 (Eulersche phi-Funktion)
- Satz 1.58 (Fermat/Euler)
- Satz 2.17 (Möbiussche Umkehrformel)
- vollkommene Zahlen (Satz 2.24)
- alle Sätze aus 3.
- Legendre-Symbol, Jacobi Symbol
- Satz 4.12 (Eulersches Kriterium) und 4.13
- Satz 4.21 (Gaußsches Lemma) und 4.22
- Theorem 4.23 (Quadratisches Reziprozitätsgesetz)
- Satz 5.1 (Euklids Satz über Pythagoräische Zahlentripel)
- Euklidischer Ring
- Quadratische Zahlkörper, ganz-algebraisch
- Satz 5.42, Satz 5.50, Satz 5.53, Satz 5.55, Satz 5.58
- Alle gelesenen Beweise zur Existenz von unendlich vielen Primzahlen.
- RSA-Verschlüsselung - alle Sätze
- Legendre-Folgen als Pseudozufallsfolgen
alte Übungen
1. Beweisen Sie, dass jede nichtleere Teilmenge der Menge der natürlichen Zahlen ein kleinstes Element enthält! Verwenden Sie hierzu nur die Peano-Axiome sowie die Eigenschaften der Ordnungsrelation "kleinergleich" aus der Vorlesung!
2. Beweisen Sie die Kommutativität von Addition sowie Multiplikation natürlicher Zahlen!
3. Finden Sie eine Lösung der Diophanitschen Gleichung 610x+377y=1.
4. Bestimmen Sie das kleinste positive x mit 133|(x-25) und 92|(x-17).
5. Beweisen Sie die Äquivalenz der folgenden 3 Aussagen über endlich viele gegebene natürliche Zahlen:
- Jede Zahl die Vielfaches jeder der gegebenen Zahlen ist, ist auch Vielfaches ihres Produkts.
- Das Produkt der gegebenen Zahlen ist ihr kleinstes gemeinsames Vielfaches.
- Die gegebenen Zahlen sind paarweise teilerfremd.
6. Beweisen Sie den Satz von Legendre über den Exponenten von p in der Primfaktorzerlegung von n!, also Theorem 1.65.
7. Schätzen Sie das Produkt der Primzahlen in {n+1,...,2n} für große n vermöge des Beweises des Bertrandschen Postulates nach unten durch eine Exponentialfunktion in n (entsprechend der letzten Anmerkung vom 13.Mai) ab!
45. Schätzen Sie beim erweiterten euklidischen Algorithmus die Größe der auftretenden Zwischenergebnisse möglichst gut in Abhängigkeit von den Eingangsdaten ab!46. Beweisen Sie, dass in jeder endlichen abelschen Gruppe die Ordnung jedes Gruppenelementes stets die maximale Ordnung eines Elementes dieser Gruppe teilt!
47. Wie kann man den Rest von ad : n effizient berechnen?
48. Warum gibt es in jeder multiplikativen zyklischen Gruppe mit gerader Ordnung höchstens zwei Zahlen, deren Quadrat 1 ist?
49. Beweisen Sie Bemerkung 1 zu Satz 7.2.
50. Bestimmen Sie RSA-Parameter um einen Klartext über einem Alphabet mit 26 Buchstaben monoalphabetisch zu verschluesseln (die Blocks sind je ein Buchstabe lang).Signieren Sie mit diesen Parametern Ihre Initialen!Was wird der Öffentlichkeit als signiertes Dokument IhrerInitialen bekanntgegeben? Was halten Sie geheim?
Hinweise:
In dieser Aufgabe geht es um das Verständnis der Schlüsselgenerierung, nicht um echte Sicherheit. Sie dürfen also mit möglichst kleinen Primzahlen arbeiten. Ein monoalphabetischer Chiffre mit einem 26-buchstabigen Alphabet ist sowieso nicht sicher.
51. Fritz, Frieda und Friedrich haben in dieser Reihenfolge die öffentlichen Schlüssel (e, n)= (3,517), (3,667) bzw. (3,697) als RSA-Parameter. Dabei ist die Länge der Klartextblöcke in Bits jeweils maximal gewaehlt. Jeder der drei bekommt eine inhaltsgleiche für ihn verschlüsselte Botschaft zugesandt. Dabei ist die Blocklänge (in Bits) für den Modul jeweils minimal gewählt. Sie bekommen folgende Bitfolgen zugeschickt:
Fritz: 01001100100100...
Frieda: 001011010100101...
Friedrich: 100001000001111...
Wie groß ist jeweils die Länge der Chiffretextblöcke und der Klartextblöcke?
Ermitteln Sie mit dem kryptoanalytischen Ansatz für kleine Exponenten den ersten Klartextblock!
Ermitteln Sie über die Faktorisierung von n die privaten Schlüssel der drei Leute!
a) Sie liefert für 2, 4, bzw. 2n (n>2) die Werte 1, 2, bzw. 2n-2.
b) Das Produkt teilerfremder Zahlen hat als Wert der Carmichael-Funktion das kgV der Werte der Carmichael-Funktion seiner Faktoren.
c) Für ungerade Primzahlen p ist die Carmichael-Funktion gleich der eulerschen Phi-Funktion.
