Zur Lösung von zahlentheoretischen Problemen mit klassischen und Quantencomputern

Schmidt, Arthur (2007)
Zur Lösung von zahlentheoretischen Problemen mit klassischen und Quantencomputern.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

URL / URN: urn:nbn:de:tuda-tuprints-8553

Kurzbeschreibung (Abstract)

In dieser Arbeit werden Algorithmen zur Lösung zahlentheoretischer Probleme für klassische Computer und Quantencomputer entwickelt und analysiert sowie ihre Auswirkungen auf Public-Key-Kryptosysteme untersucht. Im Jahr 1994 veröffentliche Shor einen Quantenalgorithmus [Shor, 1994], der das Periodengitter einer gegebenen Funktion in Quanten-Polynomzeit bestimmt. Mit diesem Algorithmus läßt sich das Faktorisierungs- und das Diskreter-Logarithmus-Problems in endlichen abelschen Gruppen in Quanten-Polynomzeit lösen. Dadurch werden die meisten heutzutage verwendeten Public-Key-Kryptoverfahren unsicher, sollten hinreichend große Quantencomputer eines Tages gebaut werden können. Der erste Quantencomputer wurde 1998 gebaut [Chuang/Vandersypen/Zhou/Leung/Lloyd, 1998]. Er bestand aus zwei Qubits. Der größte Quantencomputer, der bis heute gebaut wurde, besteht aus nur sieben Qubits [Vandersypen/Steffen/Breyta/Yannoni/Sherwood/Chuang, 2001]. Es hat sich herausgestellt, daß das Bauen von großen Quantencomputern ein extrem schwieriges Problem ist. Aus diesem Grund kann davon ausgegangen werden, daß die Größe der Quantencomputer, d.h. die Anzahl der Qubits, aus denen ein Quantencomputer besteht, nur langsam wachsen wird. Deshalb ist es von Interesse, Shors Quantenalgorithmus an verschiedene abelsche Gruppen sowie gruppenähnliche Strukturen zu adaptieren und ihre genaue Komplexität zu untersuchen, um daraus die Bedrohungen für die betroffenen Kryptosysteme genau zu bestimmen. In dieser Arbeit werden Quantenalgorithmen zur Lösung des Ordnungsproblems und des DL-Problems in der Klassengruppe der Ideale eines imaginär-quadratischen Zahlkörpers angegeben und ihre Komplexität, d.h. die Anzahl der Qubits und der elementaren Quantenoperationen, bestimmt. Darüberhinaus werden Algorithmen zur Bestimmung des Regulators und zur Lösung des Hauptidealproblems und des erweiterten Diskreter-Logarithmus-Problems in reell-quadratischen Zahlkörpern präsentiert. Shors Algorithmus wird dabei auf Funktionen angewendet, die nicht injektiv innerhalb einer Periode sind. Auch in diesem Fall wird die Komplexität der Algorithmen genau bestimmt. Im Falle von Zahlkörpern eines beliebigen Grades wird eine weitere Modifikation von Shors Algorithmus entwickelt: Es wird das Periodengitter einer Funktion bestimmt, deren Periodengitter irrational ist. Dieser Algorithmus wird benutzt, um die Einheitengruppe eines beliebigen endlich-dimensionalen Zahlkörpers zu berechnen. Als nächstes werden die Auswirkungen von Quantenalgorithmen auf die Sicherheit von Public-Key-Kryptosystemen untersucht. Es wird ein neuer Sicherheitsbegriff eingeführt. Die Sicherheit zweier Kryptosysteme wird als gleich definiert, wenn die Anzahl der Qubits zum Brechen dieser Kryptosysteme gleich ist. Basierend auf der neuen Sicherheitsdefinition wird die Geschwindigkeit und die Schlüsselgröße von einigen Kryptosystemen verglichen. Im letzten Kapitel wird ein deterministischer klassischer Algorithmus zur Berechnung der Struktur einer endlichen abelschen Gruppe aus einem Erzeugendensystem präsentiert, dessen Laufzeit nur linear von der Anzahl der gegebenen Erzeuger abhängt und dessen Speicherplatzkomplexität unabhängig von der Anzahl der gegebenen Erzeuger ist. Das stellt eine exponentielle Verbesserung zu früheren Algorithmen dar, bei denen sowohl die Laufzeit als auch die Speicherplatzkomplexität exponentiell von der Anzahl der Erzeuger im gegebenen Erzeugendensystem abhängt [Buchmann/Jacobson/Teske, 1997].

Typ des Eintrags:

Dissertation

Erschienen:

2007

Autor(en):

Schmidt, Arthur

Art des Eintrags:

Erstveröffentlichung

Titel:

Zur Lösung von zahlentheoretischen Problemen mit klassischen und Quantencomputern

Sprache:

Deutsch

Referenten:

Buchmann, Prof.Dr. Johannes ; Jacobson, Jr.; Prof. Michael John

Berater:

Buchmann, Prof.Dr. Johannes

Publikationsjahr:

27 Juli 2007

Ort:

Darmstadt

Verlag:

Technische Universität

Datum der mündlichen Prüfung:

8 Mai 2007

URL / URN:

urn:nbn:de:tuda-tuprints-8553

Kurzbeschreibung (Abstract):

Alternatives oder übersetztes Abstract:

Alternatives Abstract

Sprache

In this thesis, we will present and analyze algorithms for classical and quantum computers which solve some number theoretical problems. Moreover we will investigate their impact on current public key cryptosystems. In [Shor, 1994] Shor presented quantum algorithms which determine the period lattice of some functions in quantum polynomial time. These algorithms can be applied to solve the factoring problem and the discrete logarithm problem in finite abelian groups in quantum polynomial time. Therefore, if large quantum computers are built in the future, then almost all public key cryptosystems which are used today will be broken. The first quantum computer was built 1998 [Chuang/Vandersypen/Zhou/Leung/Lloyd, 1998]. It had two qubits. Until now, the largest quantum computer has only seven qubits [Vandersypen/Steffen/Breyta/Yannoni/Sherwood/Chuang, 2001]. Building large quantum computers seems to be an extremely difficult task. Therefore we can assume that the size of quantum computers, i.e. the number of qubits, will grow very slowly. Thus it is of interest to adapt Shor's algorithms to different abelian groups and group-like structures and to analyze their complexity closely. In this thesis, we will present algorithms which solve the order and the discrete logarithm problem in the class group of an imaginary quadratic number field. We will analyze their complexity and determine the number of qubits and elementary quantum gates which are necessary to implement these algorithms. Moreover we will present algorithms for computing the regulator and solving the principal ideal and the extended discrete logarithm problem in real quadratic number fields. Thereby, we will apply Shor's algorithm to functions which are not injective inside a period. As in the imaginary quadratic case, we will give an accurate estimation of the complexity of the presented algorithms. In the case of number fields of an arbitrary degree we will develop a further modification of Shor's algorithm. The new algorithm computes the period lattice on a function which has an irrational period lattice. We will apply this algorithm to compute the unit group of finite extensions of Q. Next, we will investigate the impact of quantum algorithms on current public key cryptosystems. We will define a new security parameter: the number of qubits which are necessary to implement an attack. Based on this new definition we will compare the speed and key sizes of some cryptosystems. In the last chapter we will present a classical algorithm that computes the structure of a finite abelian group from a generating system. Its runtime depends only linearly on the number of given generators. Its space requirements don't depend on the number of generators at all. This is an exponential improvement. Both runtime and space complexity of prior algorithms depend exponential on the number of generators in the given generating system [Buchmann/Jacobson/Teske:1997].

Englisch

Sachgruppe der Dewey Dezimalklassifikatin (DDC):

000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik

Fachbereich(e)/-gebiet(e):

20 Fachbereich Informatik

Hinterlegungsdatum:

17 Okt 2008 09:22

Letzte Änderung:

20 Mai 2018 21:23

PPN:

Referenten:

Buchmann, Prof.Dr. Johannes ; Jacobson, Jr.; Prof. Michael John