Mathematik
Refine
Year of publication
Document Type
- diplomthesis (33)
- Doctoral Thesis (30)
- Article (28)
- Book (22)
- Conference Proceeding (9)
- Contribution to a Periodical (8)
- Bachelor Thesis (7)
- Diploma 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)
Komplexität von Gitterproblemen : Nicht-Approximierbarkeit und Grenzen der Nicht-Approximierbarkeit
(2000)
Ein Gitter vom Rang n ist die Menge der ganzzahligen Linerkombinationen von n linear unabhängigen Vektoren im Rm. Unter der Annahme P <> NP beweisen wir, daß kein Polynomialzeit-Algorithmus existiert, der eine kürzeste Gitterbasis bis auf einen Faktor nO exp(1/log log n) berechnet, wobei die Länge einer Menge von Vektoren durch die maximale Euklidische Länge der Vektoren definiert ist. Weiter zeigen wir, daß eine Verbesserung dieses Resultates bis hin zu einem Faktor n/ sqrt(log n) unter plausiblen Annahmen nicht möglich ist. Ein simultaner Diophantischer Best Approximations Nenner für reelle Zahlen alpha1, .... , alpha n und Hauptnennerschranke N ist eine natürliche Zahl q mit 1 <= q >= N, so daß maxi minp2Z |q alpha i - p| minimal ist. Unter der Annahme, daß die Klasse NP keine fast-polynomiellen Algorithmen besitzt, beweisen wir, daß kein Polynomialzeit-Algorithmus existiert, der für gegebene rationale Zahlen. Ein Gitter vom Rang n ist die Menge der ganzzahligen Linerkombinationen von n linear unabhängigen Vektoren im Rm. Unter der Annahme P 6= NP beweisen wir, daß kein Polynomialzeit-Algorithmus existiert, der eine kürzeste Gitterbasis bis auf einen Faktor nO(1= log log n) berechnet, wobei die Länge einer Menge von Vektoren durch die maximale Euklidische Länge der Vektoren definiert ist. Weiter zeigen wir, daß eine Verbesserung dieses Resultates bis hin zu einem Faktor n=plog n unter plausiblen Annahmen nicht möglich ist. Ein simultaner Diophantischer Best Approximations Nenner für reelle Zahlen alpha1, .... , alpha n und Hauptnennerschranke N ist eine natürliche Zahl q mit 1 <= q <= N, so daß maxi ...... minimal ist. Unter der Annahme, daß die Klasse NP keine fast-polynomiellen Algorithmen besitzt, beweisen wir, daß kein Polynomialzeit-Algorithmus existiert, der für gegebene rationale Zahlen alpha1,......, alphan und eine Hauptnennerschranke N einen Nenner ~q mit 1 <= ~q <= f(n)N berechnet, so daß ~q bis auf einen Faktor f(n) = nO(1= log0:5+epsilon n) ein Best Approximations Nenner ist, wobei epsilon > 0 eine beliebige Konstante ist. Wir zeigen, daß eine Verbesserung dieses Resultates bis hin zu einem Faktor n=log n unter plausiblen Annahmen nicht mölich ist. Wir untersuchen die Konsequenzen dieser Resultate zur Konstruktion von im Durchschnitt schwierigen Gitterproblemen.
Gleichgewichte auf Überschussmärkten : Theorie und Anwendbarkeit auf die Regelenergiezone der RWE
(2003)
Diese Version entspricht im wesentlichen der begutachteten Version bis auf die Kürzung von Satz 3.3.1 um einen für den Rest unbedeutenden Teil. Das Ziel folgender Arbeit ist es, mit einem intuitiven Ansatz eine spezielle Wettbewerbsform zweier interagierender Märkte zu modellieren und anschließend zu analysieren. Abschließend werden die theoretischen Ergebnisse mit den Beobachtungen an einem existierenden Markt - dem deutschen Energiemarkt - verglichen. In dieser behandelten Wettbewerbsform wird ein nicht lagerbares Gut an zwei aneinander gekoppelten Märkten gehandelt. Während Handel und Preisfindung am ersten Markt den üblichen Gepflogenheiten folgen, müssen alle Teilnehmer sämtliche Güter, welche nicht unmittelbar nach Lieferung verbraucht werden, am zweiten Marktplatz (dem Überschussmarkt) gegen ein gewisses Entgelt zur Verfügung stellen. Alle Teilnehmer, welche nicht genügend Güter am ersten Markt geordert haben, werden auf dem Überschussmarkt zu einem gewissen Preis mit der noch benötigten Menge versorgt. Einem Marketmaker auf dem zweiten Marktplatz fällt die Aufgabe zu, einen Preis festzustellen, zu dem diejenigen entschädigt werden, welche ihre Überschüsse zur Verfügung stellen müssen bzw. den diejenigen zu bezahlen haben, deren Gütermangel ausgeglichen wird. Weiterhin stellt dieser sicher, dass zu jedem Zeitpunkt genügend Güter vorhanden sind, so dass der Bedarf aller Teilnehmer zu jedem Zeitpunkt sichergestellt ist. Ziel ist es nun herauszufinden, welche gewinnmaximierenden Einkaufsstrategien die Marktteilnehmer verfolgen sollten und welche Konsequenzen sich daraus auf den deutschen Energiemarkt ableiten lassen.
Ziel dieser Arbeit war es, ein sicheres und trotzdem effizientes Preprocessing zu finden. Nach den zurückliegenden Untersuchungen können wir annehmen, dies erreicht zu haben. Wir haben gezeigt, daß eine minimale Workload von Attacken von 272 mit nur 16 Multiplikationen pro Runde und 13 gespeicherten Paaren (ri, xi) erreicht werden kann. Mit der in Abschnitt 12.3 erklärten Variation - der Wert rº k geht nicht in die Gleichungen mit ein - erreichen wir sogar eine Sicherheit von 274. In diesem Fall können wir die Anzahl der gespeicherten Paare auf 12 verringern. Auch von der in Abschnit 12.5 besprochenen Variation erwarten wir eine Erhöhung der Sicherheit. Ergebnisse dazu werden bald vorliegen. Folgender Preprocessing Algorithmus erscheint z.B. nach unserem derzeitigen Wissensstand geeignet: Setze k = 12, l0 = 7, l1 = 3, d0 = 4, d1 = 5, h = 4, ¯h = 1. Initiation: lade k Paare (r0 0, x00 ) . . . , (r0 k 1, x0 k 1) mit x0i = ®r0 i mod p. º := 1. º ist die Rundennummer 1. Wähle l1 2 verschiedene Zufallszahlen a(3, º), . . . , a(l1, º) 2 {º + 1 mod k, . . . , º 2 mod k} a(1, º) := º mod k, a(2, º) := º 1 mod k W¨ahle l1 2 verschiedene Zufallszahlen f(3, º), . . . , f(l1, º) 2 {0, . . . , d1 1}, f(1, º) zuf¨allig aus {h, . . . , d1 1} und f(2, º) zuf¨allig aus {¯h, . . . , d1 1} rº k := rº ºmodk + l1 Xi=1 2f(i,º)rº 1 a(i,º) mod q xk = xºº modk · l1 Yi=1 (xº 1 a(i,º))2f(i,º) mod p 2. w¨ahle l0 1 verschiedene Zufallszahlen b(2, º), . . . , b(l0, º) 2 {º + 1 mod k, . . . , º 1 mod k} b(1, º) := º mod k W¨ahle l0 verschiedene Zufallszahlen g(1, º), . . . , g(l0, º) 2 {0, . . . , d0 1} rº ºmodk := l0 Xi=1 2g(i,º)rº 1 b(i,º) mod q xºº modk = l0 Yi=1 (xº 1 b(i,º))2g(i,º) mod p 3. verwende (rº k, xº k) f¨ur die º te Signatur (eº, yº) gem¨aß yº = rº k + seº mod q 4. º := º + 1 GOTO 1. f¨ur die n¨achste Signatur Die Zufallszahlen a(3, º), . . . , a(l, º), b(2, º), . . . , b(l, º), f(1, º), . . . , f(l, º) und g(1, º), . . . , g(l, º) werden unabhängig gewählt. Dies ist selbstverständlich nur ein Beispiel. Unsere Untersuchungen sind noch nicht abgeschlossen. Wir glauben aber nicht, daß feste Werte a(i, º) und b(i, º) ein effizientes Preprocessing definieren. Wir haben einige Variationen mit solchen weniger randomisierten Gleichungen studiert und immer effiziente Attacken gefunden.
Es steht außer Zweifel, daß digitale Signaturen schon bald zu unserem Alltag gehören wer- den. Spätestens mit dem Inkrafttreten des Gesetzes zur digitalen Signatur (siehe [BMB]) sind sie zu einem wichtigen Instrument in der Telekommunikation geworden. Dabei kommt der Verwendung von Chipkarten eine wichtige Bedeutung zu: In ihnen lassen sich die sensiblen Daten (z.B. der geheime Schlüssel) auslesesicher aufbewahren; gleichzeitig können sie bequem mitgeführt werden. Aus diesen Gründen erlebt die Verwendung von Chipkarten zur Erzeugung von digitalen Signaturen zur Zeit einen enormen Aufschwung. Problematisch ist jedoch der oft unverhältnismäßig große Berechnungsaufwand für die Erzeugung von digitalen Signaturen. Ziel dieser Arbeit ist es, Methoden zu entwickeln und/oder zu untersuchen, welche die Berechnung digitaler Unterschriften wesentlich beschleunigen. Dabei spiegelt sich die Zweiteilung der in der Praxis hauptsächlich verwendeten Typen von Signaturverfahren in der Struktur der Arbeit wider. Der erste Teil dieser Arbeit untersucht Verfahren zur effizienten Berechnung von RSA-Unterschriften. Dabei entstanden die Untersuchungen in den Abschnitten 3.2.3 und 3.2.4 in Zusammenarbeit mit R. Werchner und der Inhalt der Abschnitte 3.1 - 3.2.4 ist bereits in [MW98] veröffentlicht. Im zweiten Teil entwickeln wir Verfahren zur effizienteren Generierung von Unterschriften, die auf dem diskreten Logarithmus basieren, und untersuchen deren Sicherheit. Dabei entstanden die Untersuchungen in den Abschnitten 4.2 (bis auf 4.2.2) und 4.3.1 in Zusammenarbeit mit C. P. Schnorr und sind teilweise in [MS98] zusammengefaßt. Obwohl diese Arbeit eine mathematische Abhandlung darstellt, versuchen wir, die praktische Anwendung nicht aus den Augen zu verlieren. So orientieren sich die betrachteten Verfahren stets an den durch die verfügbare Technologie gegebenen Rahmenbedingungen. Darüber hinaus richten wir unser Augenmerk weniger auf das asymptotische Verhalten der betrachteten Verfahren, als vielmehr auf konkrete, für die Anwendung relevante Beispiele.
Eine nichtgeometrische Konstruktion der Spektren P(n) und multiplikative Automorphismen von K(n)
(1995)
Bei der Untersuchung des Langzeitverhaltens von Verzweigungsprozessen und räumlich verzweigenden Populationen ist die Betrachtung von Stammbäumen zunehmend in den Vordergrund gerückt. Probabilistische Methoden haben die in der Theorie vorherrschenden analytischen Techniken ergänzt und zu wesentlichen neuen Einsichten geführt. Die vorliegende Synopse diskutiert eine Auswahl meiner Veröffentlichungen der letzten Jahre. Den Arbeiten ist gemeinsam, dass durch das Studium der genealogischen Verhältnisse in der Population Aussagen über deren Langzeitverhalten gewonnen werden konnten. Zwei dieser Arbeiten behandeln den klassischen Galton-Watson Prozess. Eine weitere Arbeit befasst sich mit Verzweigungsprozessen in zufälliger Umgebung, sie ist technische wesentlich anspruchsvoller. Die vierte der hier besprochenen Arbeiten beschäftigt sich mit dem Wählermodell, einem der Prototypen interagierender Teilchensysteme.