TUM Logo

Prime Numbers: Complexity and Algorithms

Prime Numbers: Complexity and Algorithms  

Proseminare 2 SWS / 4,0 ECTS
Veranstalter: Alexander Malkis
Zeit und Ort:

Do, 08:00 – 09:45 Uhr, 01.08.033 (Proseminar)
Beginn: 2016-12-15

The lecture is given in english
The slides are available in english

Registration

The registration deadlines are all over. If for some reason a prospective participant failed to register in time, he/she is welcome to drop an e-mail to the instructor. The prospective participant will have to work quickly to catch up.

Contents

We are going to study the complexity and algorithms for primality testing. This is one of the most basic questions of mathematics. Slightly more formally, given the formal language

PRIMES = {binary encoding of p | p is a prime number},

we are going to show lower and upper bounds on the complexity of PRIMES of different forms.
The choice of topics:

  1. mathematical background (topic taken)
  2. the Miller-Rabin probabilistic test (topic taken)
  3. PRIMES ∈ PTIME (canceled)
  4. PRIMES ∉ AC0 (topic taken)

Previous Knowledge/Skills Expected

  • Ability to quickly obtain necessary background knowledge independently.
  • Linear algebra.
  • Complexity classes.
  • Helpful: discrete mathematics, number theory.

Objective

Understanding the basics of primality testing.

Teaching and Learning Method

The work shall be accomplished in groups of one to three participants per topic. Each group shall submit one report, one set of slides, and give one, two, or three talks. The report and the presentation(s) are strictly compulsory: their absence means a failure. All the written work shall be done in (variants of) LaTeX, possibly using (variants of) bibtex. Using more modern XeLaTeX, LuaLaTex, and/or Biber+Biblatex is welcome. We fix a common notation for all the reports and presentations. The student code of conduct must be observed.
In addition, each participant shall review one report in a double-blind way. (This is just a simulation of what is happening in conferences. In our introductory seminar, it will be virtually impossible to maintain complete anonymity. E.g., the person introducing the mathematical background will necessarily know what the others are doing and vice versa.)
In a presentation, each participant of each group shall be allocated a total of at least 20 minutes. The upper bound depends on the topic and on the distribution of work within a group.
Attending all talks and active participation in discussions is compulsory.
Every action or its absence is influencing the grade, including complying with the schedule.
The seminar language is English.

Schedule

  • ≤ 31 August: each group one obtains a topic; each group obtains its presentation date. The person speaking about mathematical background will obtain a part of his/her topics.
  • 15 September: cancellation deadline, i.e., if a student decides not to participate, he or she is kindly asked to cancel by then. If not canceled, informally report on progress.
  • ≤ 30 September: each group communicates mathematical backgrounds it needs to the participant presenting the mathematical backgrounds. Second informal report on progress.
  • ≤ 6 weeks before the first presentation of a group: submit the report and the slides in (source and (PDF or Postscript)) without the authors' names on the documents,
  • at an arbitrary time point each participant obtains one report for a double-blind review, which he or she has to accomplish within 2 weeks.
  • ≤ 27 days (= 4 weeks - 1 day) before the first presentation of a group: obtain feedback on one's own report. Since the feedback is done by the other participants, the timely presence of the feedback or its quality are not guaranteed.
  • ≤ 2 weeks before the first presentation of a group: submit the final versions of the group's report and slides with the author's names. The contribution of each participant to the report shall be clearly stated.
  • directly after a presentation: obtain feedback from the instructor on the talk and on the slides.
  • ≤ 1 week after the last presentation of a group: obtain feedback from the instructor on the report.
  • ≥ 1 week after the last presentation of a group: grade goes formally to TUMonline.

Talk timetable:

mathematical background 15.12.2016
Miller-Rabin probabilistic test 22.12.2016
PRIMES ∈ PTIME (canceled) 12.01.2017
(canceled) 19.01.2017
(canceled) 26.01.2017
PRIMES ∉ AC0 02.02.2017
(continued) 09.02.2017

Scientific Material

Online:

Books:

  • P. Ribenboim, Die Welt der Primzahlen. Springer. 2008.
  • M. Dietzfelbinger, Primality testing in polynomial time. Lecture Notes in Computer Science. 2004.
  • C. Karpfinger, H. Kiechle: Kryptologie. Springer. 2010.
  • R. Waldecker, L. Rempe-Gillen: Primzahltests für Einsteiger. Vieweg+Teubner Verlag. 2009.
  • S. Y. Yan: Primality testing and integer factorization, 2nd edition. Springer. 2009.
  • J. Buchmann: Einführung in die Kryptographie. Springer. 2010.

On [PDF|Xe|Lua]LaTeX