Mathematik
Refine
Year of publication
Document Type
- diplomthesis (32)
- Doctoral Thesis (30)
- Article (28)
- Book (22)
- Conference Proceeding (9)
- Contribution to a Periodical (8)
- Diploma Thesis (8)
- Bachelor Thesis (7)
- Master's Thesis (6)
- Report (6)
Language
- German (160) (remove)
Has Fulltext
- yes (160)
Is part of the Bibliography
- no (160)
Keywords
- Doku Mittelstufe (4)
- Doku Oberstufe (4)
- Stochastik (4)
- Finanzmathematik (3)
- Mathematik (3)
- Statistik (3)
- Arithmetische Gruppe (2)
- Biographie (2)
- Frankfurt <Main> / Universität (2)
- Martingal (2)
Institute
- Mathematik (160)
- Präsidium (22)
- Psychologie (6)
- Geschichtswissenschaften (5)
- Informatik (5)
- Physik (5)
- Sportwissenschaften (5)
- Biochemie und Chemie (3)
- Biowissenschaften (3)
- Geographie (3)
In dieser Arbeit werden die mathematischen Grundlagen zur Konstruktion der primären Felder der minimalen Modelle der konformen Quantenfeldtheorie beschrieben. Wir untersuchen Verma und Fock-Moduln der Virasoro-Algebra und klassifizieren diese Moduln bezüglich der Struktur der (ko-) singulären Vektoren. Wir definieren die Vertex-Operatoren zwischen gewissen Fock-Moduln (die eine kanonische Hilbertraumstruktur besitzen) und beweisen verschiedene Eigenschaften dieser Operatoren: Unter bestimmten Voraussetzungen sind Vertex-Operatoren dicht definierte, nicht abschließbare Operatoren zwischen den Fock-Moduln. Radialgeordnete Produkte von Vertex-Operatoren existieren auf einem dichten Teilraum. Wir beweisen Kommutatorrelationen zwischen Vertex-Operatoren und den Generatoren der Virasoro-Algebra. Dann definieren wir die integrierten Vertex-Operatoren und zeigen, daß diese Operatoren im wesentlichen wieder die Eigenschaften der nichtintegrierten Vertex-Operatoren haben. Gewisse integrierte Vertex-Operatoren können mit konformen Felder identifiziert werden. Ein unter den Vertex-Operatoren invarianter Unterraum der Fock-Moduln kann mit dem physikalischen Zustandsraum identifiziert werden.
Über die Anzahlfunktion π(x)
(1999)
Bereits Euklid wusste, dass es unendlich viele Primzahlen gibt. Euler zeigte die qualitative Aussage ¼(x) x ! 0 bei x ! 1. Legendre definierte als erster die Anzahlfunktion ¼(x) als die Anzahl aller Primzahlen · x, (x 2 R) und vermutete irrtümlicherweise, dass ¼(x) = x log(x)¡B; wobei lim x!1 B(x) = 1; 083 66 : : : ist. Gauss vermutete, dass die Funktionen ¼(x) und li(x) := lim "!0 ">0 0@ u=1¡" Z u=0 du log(u) + u=x Z u=1+" du log(u)1A asymptotisch Äquivalent sind. Tschebyschew konnte die Legendresche Vermutung widerlegen; außerdem bewies er: Wenn der Grenzwert lim x!1 ¼(x) x log(x) existiert, so muss dieser gleich 1 sein. Dank wegweisender Vorarbeiten von Riemann, gelang es im Jahr 1896 unabhängig voneinander und nahezu zeitgleich Hadamard und De La Vallee Poussin, den Primzahlsatz analytisch zu beweisen. Beide verwendeten entscheidend die Tatsache, dass die Zetafunktion ³ in der Halbebene Re(s) ¸ 1 nicht verschwindet. Die Beweise waren zuerst so lang und kompliziert, dass sie heutzutage nur noch einen historischen Wert besitzen. Es dauerte weitere 84 Jahre bis der Beweis so vereinfacht werden konnte, dass er nur wenige Seiten in Anspruch nimmt. Ein wichtiger Verdienst kommt hierbei der Arbeit von Newman aus dem Jahre 1980 zu. Lange Zeit wurde es für kaum möglich gehalten, einen Beweis des Primzahlsatzes zu finden, der ohne eine gewisse Kenntnis der komplexen Nullstellen der Zetafunktion auskommt. Und doch glückte 1948 ein solcher Beweis durch Selberg und Erdös mit elementaren Mitteln. Erwähnenswert dabei, dass der Beweis noch lange nicht einfach ist. Uns schienen die analytischen Beweise durchsichtiger zu sein. Daher haben wir in dieser Arbeit auf einen elementaren Beweis verzichtet. Der analytischen Weg zum Primzahlsatz von Newman kommt einerseits mit Integration längs endlicher Wege (und der Tatsache ³(s) 6= 0 in ¾ ¸ 1) aus, umgeht also Abschätzungen bei 1; andererseits ist er frei von Sätzen der Fourier-Analysis. Beim Beweis des Primzahlsatzes von Wolke benutzt man anstelle von ³0(s) ³(s) die Funktion ³ 1 k mit großen k. Wegen des Pols bei s=1 bringt dies bei der Integration leichte Komplikationen, hat aber den Vorteil, dass außer der Nullstellen-Freiheit keine nichttriviale Abschätzung für ³ oder ³0 erforderlich ist. Dank der elementaren Äquivalenz zwischen dem Primzahlsatz und der Konvergenz von 1Pn=1 ¹(n) n brauchte Newman nur die Konvergenz von 1Pn=1 ¹(n) n zu zeigen. Dies erreichte er mit Hilfe seines Konvergenzsatzes. Die Legendresche Formel, die auf dem Sieb des Eratosthenes basiert, erlaubt die exakte Berechnung von ¼(x), wenn alle px nicht übersteigenden Primzahlen bekannt sind. Diese prinzipielle Möglichkeit zur Ermittlung von ¼(x) ist in der Praxis natürlich stark limitiert durch die mit x rasch anwachsende Anzahl der rechts in der Legendresche Formel zu berücksichtigenden Summanden. Mit verfeinerten Siebtechniken haben verschiedene Autoren zur Legendresche Formel analoge Formeln ¼(x) ersonnen, bei denen der genannte Nachteil von Legendresche Formel sukzessive reduziert wurde. Zu erwähnen sind hier vor allem Meissel, Lehmer, sowie Lagarias, Miller und Odlyzko. Aus den Graphen von R(x)¡¼(x); li(x)¡¼(x) und x log(x) ¡¼(x) für den betrachteten Bereich x · 1018 konnten wir feststellen, dass R(x); li(x) sowie x log(x) die Anzahlfunktion Pi (x) annähern, wobei R(x) die beste Approximation für Pi(x) von allen drei ist.
Im Mittelpunkt der vorliegenden Arbeit stehen die Nullstellen der nach Bernhard Riemann benannten Riemannschen Zetafunktion ..(s). Diese Funktion kann für komplexes s mit Res > 1 durch ...(s) = 1 X n=1 1 ns (1.1.1) dargestellt werden. Für andere Werte von s ist ...(s) durch die analytische Fortsetzung der Dirichlet-Reihe in (1.1.1) gegeben. Die ...-Funktion ist in der ganzen komplexen Ebene holomorph, mit Ausnahme des Punktes s = 1, wo sie einen einfachen Pol besitzt. Diese und weitere Eigenschaften von ...(s) setzen wir in dieser Arbeit als bekannt voraus, näheres findet man beispielsweise in [Tit51] oder [Ivi85]. Bereits Euler betrachtete, beispielsweise in [Eul48, Caput XV], die Summe in (1.1.1), allerdings vor allem für ganzzahlige s ... 2. Von ihm stammt die Gleichung 1 X n=1 1 ns =.... die für alle komplexen s mit Res > 1 gültig ist. Dieser Zusammenhang zwischen der ...-Funktion und den Primzahlen war Ausgangspunkt für Riemanns einzige zahlentheoretische, aber dennoch wegweisende Arbeit \ Über die Anzahl der Primzahlen unter einer gegebenen Grösse." ([Rie59]). In dieser 1859 erschienenen Arbeit erkannte Riemann als erster die Bedeutung der Nullstellen der ...-Funktion für die Verteilung der Primzahlen. Bezüglich dieser Nullstellen sei jetzt nur so viel gesagt, daß ...(s) einfache Nullstellen an den negativen geraden Zahlen .... besitzt, und, daß alle weiteren, die sogenannten nicht-trivialen Nullstellen, im kritischen Streifen 0 < Res < 1 liegen. Diese letzteren | unendlich vielen | Nullstellen sind gerade für den Primzahlsatz, also für die Beziehung ...(x) ... li(x);
Wir behandeln Kettenbruchentwicklungen in beliebiger Dimension. Wir geben einen Kettenbruchalgorithmus an, der für beliebige Dimension n simultane diophantische Approximationen berechnet, die bis auf den Faktor 2 exp (n+2)/4 optimal sind. Für einen reellen Eingabevektor x := (x1,...,X n-1, 1) berechnet der Algorithmus eine Folge ganzzahliger Vektoren ....., so daß für i =1, ...., n-1 : | q exp (k) xi -pi exp (k)| <= 2 exp (n+2)/4 sqrt (1 + xi exp 2) / q exp (1/n-1). Nach Sätzen von Dirichlet und Borel ist die Schranke optimal in dem Sinne, als daß der Exponent 1/(n-1) im allgemeinen nicht erhöht werden kann. Der Algorithmus konstruiert eine Folge von Gitterbasen des Zn, welche die Gerade x R approximieren. Für gegebenes E > 0 findet der Algorithmus entweder eine Relation zu x, das heißt einen ganzzahligen zu x orthogonalen Vektor (ungleich Null), mit euklidischer Länge kleiner oder gleich E exp -1, oder er schließt Relationen zu x mit euklidischer Länge kleiner als E exp -1 aus. Der Algorithmus führt in der Dimension n und |log E| polynomial viele arithmetische Operationen auf rellen Zahlen in exakter Arithmetik aus. Für rationale Eingaben x := (p1, ....., pn)/pn, E>0 mit p1,.....,pn Teil von Z besitzt der Algorithmus polynomiale Bitkomplexität in O........ Eine Variante dieses Algorithmus konstruiert für Eingabevektoren x einen (von x nicht notwendigerweise verschiedenen) Nahebeipunkt x' zu x und eine kurze Relation zu x'. Im Falle x<>x können wir die Existenz von Relationen kleiner als (2E)exp -1 für Punkte in einer kleinen offenen Umgebung um x' ausschließen. Wir erhalten in diesem Sinne eine stetige untere Schranke für die Länge der kürzesten Relation zu Punkten in dieser Umgebung. Die für x' berechnete Relation ist bis auf einen in der Dimension n exponentiellen Faktor kürzeste Relation für x'. Zur Implementierung des Kettenbruchalgorithmus stellen wir ein numerisch stabiles Verfahren vor und berichten über experimentelle Ergebnisse. Wir geben untere Schranken für die Approximierbarkeit kürzester Relationen in der Maximum-Norm und minimaler diophantischer Approximationen an: Unter der Annahme, daß die Klasse NP nicht in der deterministischen Zeitklasse O(n exp poly log n) enthalten ist, zeigen wir: Es existiert kein Algorithmus, der für rationale Eingabevektoren x polynomial in der Bitlänge bin(x) von x ist und die in der Maximum-Norm kürzeste Relation bis auf einen Faktor 2 exp (log 0.5 - zeta bin(x)) approximiert. Dabei ist zeta eine beliebig kleine positive Konstante. Wir übertragen dieses Resultat auf das Problem, zu gegebenen rationalen Zahlen x1,....,xn-1 und einem rationalen E > 0 gute simultane diophantische Approximationen zu finden, das heißt rationale Zahlen p1/q,...; (p n-1/)q mit möglichst kleinem Hauptnenner q zu konstruieren, so daß max 1 <=i <= n-1 |q xi - pi| <= E. Wir zeigen unter obiger Annahme, daß kein Algorithmus existiert, der für gegebene rationale Zahlen x1,........,x n-1 und natürlicher Zahl N polynomial-Zeit in der Bitlänge bin(x) von x ist und simultane diophantische Approximationen berechnet, so daß max 1 <=i <= n-1 |q xi - pi| für q gehört zu [1, N] bis auf den Faktor 2 exp (log 0.5 - zeta bin(x)) minimal ist. Hierbei ist zeta wieder eine beliebig kleine positive Konstante.
In der vorliegenden Arbeit wird ein interaktives Beweisprotokoll für das Problem der "überprüfbaren Verschlüsselung" (verifiable encyption) vorgestellt. Mit Hilfe eines Verifiable Encryption Protokolls (VEP) beweist eine Person (der Prover) einer anderen Person (dem Verifier) effizient, daß ein vorher gesendeter Wert alpha die Verschlüsselung eines geheimen Wertes s ist. Den geheimen Wert s muß er dazu nicht offenlegen. Zur Verschlüsselung von s wird ein Public-Key-Verfahren und ein öffentlicher Schlüssel PK benutzt. PK gehört zum Schlüsselpaar einer dritten Partei, die nicht aktiv an der Protokollausführung beteiligt ist und die Rolle eines Notars einnimmt. Dem Verifier steht ein Wert d zur Verfügung, anhand dessen er entscheidet, ob er den Beweis akzeptiert oder verwirft. Akzeptiert der Verifier den Beweis des Provers, so kann er zwar mit an Sicherheit grenzender Wahrscheinlichkeit sagen, daß alpha eine Verschlüsselung von s unter dem öffentlichen Schlüssel PK ist. Er kann s jedoch nicht rekonstruieren, da er nicht im Besitz des zu PK gehörigen geheimen Schlüssels SK ist und der Beweis keine Informationen über s preisgibt.
Gitter sind diskrete, additive Untergruppen des IRm, ein linear unabhängiges Erzeugendensystem eines Gitters heißt Gitterbasis. Die Anzahl der Basisvektoren eines Gitters ist eindeutig bestimmt und heißt Rang des Gitters. Zu jedem Gitter vom Rang n gibt es mehrere Gitterbasen, die man alle erhält, indem man eine Basismatrix B = [b1, · · · , bn] von rechts mit allen Matrizen aus der Gruppe GLn(ZZ) multipliziert. Eine wichtige Fragestellung der Gittertheorie ist es, zu einem gegebenen Gitter einen kürzesten, vom Nullvektor verschiedenen Gittervektor zu finden. Dieses Problem heißt das kürzeste Gittervektorproblem . Ein dazu verwandtes Problem ist das "nächste Gittervektorproblem", das zu einem beliebigen Vektor x aus IRm einen Gittervektor sucht, dessen Abstand zu x minimal ist. Aus dem "kürzesten Gittervektorproblem" entwickelte sich die Gitterbasenreduktion, deren Ziel es ist, eine gegebene Gitterbasis in eine Gitterbasis zu transformieren, deren Vektoren bzgl. der Euklidischen Norm kurz und möglichst orthogonal zueinander sind. Wichtig für die Güte einer Reduktion ist der Begriff der sukzessiven Minima ¸1(L), · · · , ¸n(L) eines Gitters L. Dabei ist ¸i(L) die kleinste reelle Zahl r > 0, für die es i linear unabhängige Vektoren cj 2 L gibt mit kcjk · r für j = 1, · · · , i. Man versucht, für ein Gitter L eine Gitterbasis b1, · · · , bn zu finden, bei der die Größe kbik / ¸i(L) für i = 1, · · · , n möglichst klein ist. Für Gitter vom Rang 2 liefert das Gauß'sche Reduktionsverfahren eine Gitterbasis mit kbik = ¸i(L) für i = 1, 2. Eine Verallgemeinerung der Gauß-Reduktion auf Gitter mit beliebigem Rang ist die im Jahre 1982 von Lenstra, Lenstra, Lovasz vorgeschlagene L3-Reduktion einer Gitterbasis, deren Laufzeit polynomiell in der Bitlänge der Eingabe ist. L3-reduzierte Gitterbasen approximieren die sukzessiven Minima bis auf einen (im Rang des Gitters) exponentiellen Faktor. Die vorliegende Arbeit besteht aus zwei Teilen. Im ersten Teil (Kapitel 1-6) wird ein neues Reduktionskonzept von M. Seysen aus der Arbeit "A Measure for the Non-Orthogonality of a Lattice Basis" behandelt und im zweiten Teil (Kapitel 7) ein aktuelles Ergebnis von M. Ajtai über die Faktorisierung ganzer Zahlen aus "The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions"[2]. Seysen führte in [13] zu einer gegebenen Gitterbasis b1, · · · , bn die Größe ¾(A) ein, die nur von den Einträgen der zugehörigen Gram-Matrix A = [b1, · · · , bn]T · [b1, · · · , bn] und der Inversen A 1 abhängt. Sie hat die Eigenschaft, daß für jede Gitterbasis b1, · · · , bn mit Gram-Matrix A gilt, daß ¾(A) ¸ 1, wobei die Gleichheit genau dann gilt, wenn b1, · · · , bn orthogonal ist. Aus dieser Defintion ergibt sich folgender Reduktionsbegriff: Eine Gitterbasis b1, · · · , bn mit Gram-Matrix A heißt genau dann ¿ -reduziert, wenn ¾(A) minimal für alle Basen des Gitters ist. Der wesentliche Unterschied der ¿-Reduktion zur L3-Reduktion ist, daß die Größe ¾(A) unabhängig von der Reihenfolge der Basisvektoren ist, so daß eine ¿ -reduzierte Gitterbasis bei beliebiger Permutation der Basisvektoren ¿ -reduziert bleibt. Die ¿-Reduktion reduziert also im Gegensatz zur L3-Reduktion die Basisvektoren gleichmäßig. Seysen zeigte, daß man zu jedem Gitter vom Rang n eine Gitterbasis mit Gram-Matrix A findet, so daß ¾(A) durch eO((ln n)2) beschränkt ist. Daraus läßt sich ableiten, daß ¿ -reduzierte Gitterbasen eines Gitters vom Rang n die sukzessiven Minima bis auf den Faktor eO((ln n)2) approximieren. Da es sich bei der ¿-Reduktion um einen sehr starken Reduktionsbegriff handelt, für den es schwer ist, einen effizienten Algorithmus zu finden, definiert man folgenden schwächeren Reduktionsbegriff: b1, · · · , bn heißt genau dann ¿2-reduziert, wenn keine Basistransformation der Form bj := bj +k · bi mit 1 · i 6= j · n und k 2 ZZ die Gr¨oße ¾(A) erniedrigt. Für n = 2 entspricht die ¿-Reduktion sowohl der ¿2- Reduktion als auch der Gauß-Reduktion. Für die ¿2-Reduktion findet man einen effizienten Algorithmus. Wendet man diesen Algorithmus auf Rucksackprobleme an, so ergibt sich, daß durch einen Algorithmus, bestehend aus ¿2-Reduktion und anschließender L3-Reduktion, bei großer Dichte und bei kleiner Dimension wesentlich mehr Rucksackprobleme gelöst werden als durch den L3-Algorithmus. Die Faktorisierung großer ganzer Zahlen ist ein fundamentales Problem mit großer kryptographischer Bedeutung. Schnorr stellte in [11] erstmals einen Zusammenhang zwischen Gitterbasenreduktion und Faktorisierung her, indem er das Faktorisieren ganzer Zahlen auf das "nächste Gittervektorproblem in der Eins-Norm" zurückführte. Adleman führte in [1] das Faktorisieren ganzer Zahlen sogar auf das "kürzeste Gittervektorproblem in der Euklidischen Norm" zurück, allerdings unter zahlentheoretischen Annahmen. In [2] stellte Ajtai ein neues Ergebnis vor, in dem er das Faktorisieren ganzer Zahlen auf das "kürzeste Gittervektorproblem in der Euklidischen Norm" ohne zusätzliche Annahmen zurückführte.
Der Begriff der editierfreundlichen Kryptographie wurde von Mihir Bellare, Oded Goldreich und Shafi Goldwasser 1994 bzw. 1995 eingeführt. Mit einem editierfreundlicher Verschlüsselungs- oder Unterschriftenverfahren kann man aus einer Verschlüsselung bzw. Unterschrift zu einer Nachricht schnell eine Verschlüsselung oder Unterschrift zu einer ähnlichen Nachricht erstellen. Wir geben eine Übersicht über die bekannten editierfreundlichen Verfahren und entwickeln sowohl ein symmetrisches als auch ein asymmetrisches editierfreundliches Unterschriftenverfahren (IncXMACC und IncHSig). Wir zeigen, wie man mit editierfreundlichen Schemata überprüfen kann, ob die Implementierung einer Datenstruktur korrekt arbeitet. Basierend auf den Ideen der editierfreundlichen Kryptographie entwickeln wir effiziente Verfahren für spezielle Datenstrukturen. Diese Ergebnisse sind in zwei Arbeiten [F97a, F97b] zusammengefaßt worden.
In der vorliegenden Diplomarbeit beschäftigen wir uns mit kryptographisch sicheren Pseudozufallsgeneratoren. Diese e±zienten Algorithmen erzeugen zu zufälliger Eingabe deterministisch eine längere Bitfolge, die praktisch von einer Folge zufälliger Münzwürfe nicht unterscheidbar ist. Wir geben die Definitionen von A. Yao sowie M. Blum und S. Micali, beweisen die Äquivalenz und charakterisieren den Unterschied zur klassischen Sichtweise von Zufallsgeneratoren. Mit der Blum-Micali-Konstruktion zeigen wir, wie man aus einer Oneway-Permutation und zugehörigem Hardcore-Prädikat einen kryptographisch sicheren Pseudozufallsgenerator konstruiert: Man wendet auf einen zufälligen Startwert iterativ die Oneway-Funktion an und gibt jeweils das Hardcore-Prädikat des Urbilds aus. Wir stellen das allgemeine Hardcore- Prädikat inneres Produkt modulo 2 von L.A. Levin und O. Goldreich vor und beweisen mit Hilfe des XOR-Lemmas von U.V. Vazirani und V.V. Vazirani die Verallgemeinerung zu einer Hardcore-Funktion, die statt eines Prädikats mehrere Bits ausgibt. Man geht davon aus, daß die Verschlüsselungsfunktionen des RSA- und des Rabin-Public- Key-Kryptosystems Oneway-Permutationen sind. Basierend auf dem Rabin-System haben L. Blum, M. Blum und M. Shub den x2-mod-N-Generator aufgebaut, W. Alexi, B. Chor, O. Goldreich und C.P. Schnorr haben den RSA-Generator konstruiert und den Sicherheitsbeweis zum x2-mod-N-Generator verbessert. Diese Generatoren basieren auf der Blum-Micali-Konstruktion mit dem Hardcore-Prädikat des untersten Bits. Durch neue Ideen können wir die beweisbare Sicherheit der Generatoren deutlich erhöhen, so daß in der Praxis kleinere Schlüssellängen genügen. Bisher war zum Beispiel für den x2-mod-N-Generator bekannt, daß man mit einem Algorithmus A, der das unterste Bit der Wurzel modulo einer n-Bit- Blumzahl mit Wahrscheinlichkeit 1 2 + ² in Zeit |A| = ¡n3¢ berechnet, den Modul in Zeit O¡n3² 9|A|¢ mit Wahrscheinlichkeit ²2 64 faktorisieren kann. Wir verbessern die Laufzeit zu O¡n² 4 log2(n² 1)|A|¢ und Wahrscheinlichkeit 1 9 . Diese neuen Resultate wurden auf der Eurocrypt-Konferenz im Mai 1997 in Konstanz vorgestellt, D.E. Knuth hat sie bereits in die neue Auflage seines Standardwerks The Art of Computer Programming aufgenommen.