Primzahlen, geheime Codes und die Grenzen der Berechenbarkeit

Die Primzahlen gehören zu jenen mathematischen Objekten, welche seit jeher alle mathematisch Interessierten fasziniert haben. Jede Zahl setzt sich aus Primzahlen zusammen, die Primzahlen sind also sozusagen die Atome des Zahlensystems, mit dem alle Mathematik beginnt. Umso erstaunlicher mutet es an, dass einige der ältesten Primzahlprobleme trotz größter Bemühungen von Generationen von Mathematikern bis heute ungelöst sind. Es gibt aber noch einen weiteren, nicht weniger erstaunlichen Aspekt. Die Zahlentheorie galt jahrhundertelang neben der Euklidischen Geometrie als das klassische Modell der reinen Mathematik: ein theoretisches Gebäude voller Schönheit und Eleganz, ein Kunstwerk des menschlichen Geistes. Seit etwa 20 Jahren hat sich dies geändert: Die Primzahlen sind auch in das Zentrum der Anwendungen gerückt. Sie spielen, wie wir sehen werden, eine entscheidende Rolle bei geheimen Codes, die heute aus unserem „codierten“ Leben nicht mehr wegzudenken sind. Und schließlich führen Primzahlen geradewegs zu einer der wichtigsten Fragen im Zeitalter der Informationstechnik: Was können Computer, bzw. wo liegen prinzipiell die Grenzen der Berechenbarkeit? Über diese drei Teile, wie im Titel angekündigt, wollen wir uns im Folgenden unterhalten.