08 053150 Research in Groups: Number Theory and Quantum Computing
Lecturer: Jörn Steuding
Dates: Mo 14-16, Tu 10-12, SE 30,
We begin: Mo, 29 April 2019, 14:15 a.m.
Short summary: The very first investigations on the role of quantum mechanics in the theory of computations are due to Paul Benioff and Richard Feynman in the 1980s and led to the idea of a quantum computer. Their computing power would rely on the laws of quantum mechanics and the entanglement of quantum states would yield something which is best compared with operating many classical computers parallel. Although this thought experiment may have been considered as utopian science fiction in the very beginning, recent progress on both, theoretical and practical details since the 1990s has turned this topic into a vivid branch of modern research in computer science and mathematics. Now it is clear that the realization of such a quantum device would outshine classical computers in many real-life applications, e.g., in cryptography. The probably most striking example is Peter Shor's quantum algorithm for factoring large integers (for which he was awarded the Nevanlinna Prize at the International Congress of Mathematicians in Berlin in 1998) which would make classical cryptosystems (as, for example, the widely used RSA) attackable. Of course, this weakness has ever since this discovery been the starting point of research for secure cryptosystems even under the rule of quantum computers. With so-called quantum error-correcting codes there are also unrestricted positive examples of quantum computation. In the course, we shall first recall some basics from (elementary) number theory (e.g., the Euclidean algorithm and continued fractions), elliptic curves (the group law for curves over finite fields), and classical cryptography (including the Diffie-Hellman key exchange, ElGamal, RSA, and zero knowledge); then we proceed with an introduction to quantum computation (which relies essentially on linear algebra and the theory of Hilbert spaces) and discuss quantum algorithms as, for example, the aforementioned Shor's factoring algorithm (and the algorithms of Deutsch and Jozsa). Finally, we present recent ideas about a post-quantum cryptosystem due to Luca De Feo, David Jao and Jérôme Plût that relies on the arithmetic of elliptic curves and some graph theory.
- Yorick Hardy and Willi-Hans Steeb, Classical and Quantum Computing, Birkhäuser 2001
- Neal Koblitz, A Course in Number Theory and Cryptography, Springer, 2nd ed. 1994
- Arthur O. Pittenger, An Introduction to Quantum Computing Algorithms, Birkhäuser 2000
0800220 Introduction to Number Theory
0800225 Exercises for Introduction to Number Theory
Lecturer: Jörn Steuding
Dates: Lecture: 4 hours, Wed+Thu 10-12, HS A in the chemistry building; Tutorials: 2 hours., Mon 10-12, 12-14, Tue 10-12, S0.106, 14-16, S0.107
We begin: Wed, 26 April 2019, 10:15 a.m.
Short summary: Number theory is a traditional discipline with many modern facets and applications (e. g. in cryptography). It deals with the arithmetic of integers and rational numbers (and also other "types" of numbers). In this introduction we deal with the foundations of classical number theory: elementary divisibility properties, modular arithmetic, structure of residual class rings, quadratic reciprocity law, cyclotomy, diophantine approximation and diophantine equations, quadratic forms, lattices and questions on the distribution of prime numbers. The lecture also presents some well-known open problems.
- A. Baker, A concise introduction to the theory of numbers, Cambridge University Press 1984. (Kurz, prägnant und elegant!)
- P. Bundschuh, Einführung in die Zahlenthorie, Springer 2002, 5. Auflage. (Standardwerk der deutschsprachigen Literatur mit vielen historischen Bemerkungen!)
- G.H. Hardy & E.M. Wright, An introduction to the theory of numbers, Clarendon Press 1979, 5th ed. (Der Klassiker, der fast alles enthält!)
- M. Hindry, Arithmétique, Calvage & Mounet 2008. (Sehr ansprechende moderne Darstellung aus einer interessanten Perspektive!)
- N. Oswald, J. Steuding, Elementare Zahlentheorie, Springer 2014
- W. Scharlau & H. Opolka, Von Fermat bis Minkowski, Springer 1980. (Eine historisch motivierte Einführung!)
- J. Steuding, Diophantine Analysis , CRC-Press/Chapman Hall 2005.
- J. Steuding, Einführung in die Zahlentheorie, Kurzskript der Vorlesung 2013
- J. Wolfart, Einführung in die Zahlentheorie und Algebra, Vieweg 1996.(Betont all die wichtigen Bezüge zur Algebra!)