Rebecca Waldecker ist Professorin für Algebra an der Martin-Luther-Universität Halle-Wittenberg. Sie besuchte Karlsruhe aus Anlass einer Konferenz zu Ehren von Richard Weiss und Gudrun nutzte die Gelegenheit, um mit ihr über das Faszinosum und die Nützlichkeit von Primzahlen und ihr Forschungsgebiet der Gruppentheorie zu sprechen.

• Eine Primzahl ist eine natürliche Zahl, die genau zwei verschiedene natürliche Teiler hat – sich selbst und 1.

Die Zahl 1 ist damit keine Primzahl, aber z.B. ist die Zahl 2 prim sowie die Zahlen 3, 5, 7, 11, 13, 17, 19 usw. Ein grundlegendes Resultat besagt, dass sich alle natürlichen Zahlen eindeutig in Produkte von Primzahlen aufteilen lassen. Zahlen, die selbst nicht prim sind, nennt man deshalb zerlegbar bzw. zusammengesetzt, weil man sie mit Hilfe dieser Darstellung in die zugehörigen Primfaktoren aufteilen kann bzw. man diese als Grundbausteine der natürlichen Zahlen ansehen kann.

Es gibt in diesem Zusammenhang viele interessante Fragen. Zum Beispiel:

1. Wie viele Primzahlen gibt es?
2. Gibt es beliebig große Primzahlzwillinge, d.h. zwei Primzahlen, die voneinander nur den Abstand 2 haben (wie z.B. 11 und 13)?
3. Wie kann ich eine Zahl als Primzahl erkennen?
4. Wie kann ich für jede Zahl (effektiv) die Zerlegung in Primfaktoren berechnen?

Interessant ist, dass diese Fragen, die doch eher theoretisch und fast schon spielerisch wirken, heute eine große Relevanz erhalten, weil sich alle gebräuchlichen digitalen Verschlüsselungsverfahren (z.B. beim online-Banking) großer Primzahlen bedienen (je größere Primzahlen man verwenden kann, desto sicherer ist die zugehörige Verschlüsselung). Das liegt daran, dass es im Allgemeinen tatsächlich eine recht lange Rechenzeit braucht, um große Zahlen in mögliche Primfaktoren zu zerlegen.

Wenn man sich jedoch davon löst, Primzahlen und Teiler nur auf natürliche Zahlen zu beziehen, wird die Welt noch ein wenig interessanter. Besonders einfach und fast offensichtlich ist es bei der Ausweitung auf ganze Zahlen. In den ganzen Zahlen gibt es mehr Teiler: Zum Beispiel hat die Zahl 3 dort (neben 3 und 1) auch noch die Teiler -1 und -3. Man muss dann entscheiden, welches die Grundbausteine für ganze Zahlen sein sollen.

Noch etwas allgemeiner ausgedrückt: Wenn der Begriff der Primzahl auf andere Zahlbereiche verallgemeinert wird, dann gibt es zwei Eigenschaften, die man als charakterisch für "prim" ansehen kann: Einerseits die "Unzerlegbarkeit", also die Eigenschaft, nur die offensichtlichen Teiler zu besitzen. Primzahlen haben aber auch die Eigenschaft (im Bereich der ganzen Zahlen), dass, wenn sie ein Produkt von Zahlen teilen, sie automatisch mindestens einen der Faktoren teilen. Auch diese Eigenschaft kann man zur Verallgemeinerung der Eigenschaft "prim" benutzen.

Häufig ist es so, dass in der Übertragung der Idee auf Objekte, die die Struktur eines algebraischen Rings haben (d.h. grob gesprochen, man "rechnet" in ihnen mehr oder weniger so, wie wir es von den ganzen Zahlen kennen) die Unzerlegbarkeit mit dem Begriff "irreduzibel" verallgemeinert wird und dass die andere Eigenschaft (wenn man ein Produkt teilt, dann auch mindestens einen der Faktoren) mit "prim" oder "Primelement" verallgemeinert wird. In manchen Zahlbereichen fallen diese Begriffe zusammen. Zum Beispiel ist das bei den ganzen Zahlen so und bei den im Gespräch erwähnten Ganzen Gaußschen Zahlen.

Die Ganzen Gaußschen Zahlen werden aus allen Punkten mit ganzzahligen Koordinaten in der Gaußschen Zahlenebene gebildet. Diese Ebene ist eine geometrische Interpretation der Menge der komplexen Zahlen – die beiden Achsen geben Real- und Imaginärteil der jeweiligen komplexen Zahl an. Wählt man alle ganzzahligen Punkte, so ergibt das eine Struktur, die geometrisch betrachtet ein Gitter ist, und die algebraisch betrachtet den ganzen Zahlen nicht unähnlich ist. Allerdings wird die Multiplikation etwas interessanter, deshalb ändern sich die Eigenschaften von Primzahlen im Ring der Ganzen Gaussschen Zahlen.

• 2 ist dort keine Primzahl, sondern hat neben den offensichtlichen Teilern 2,-2,1,-1,i,-i,2i,-2i auch noch die Teiler 1+i, 1-i und noch einige mehr.
• Alle Primzahlen, die beim Teilen durch 4 in den Rest 3 lassen, bleiben prim in . Zum Beispiel 3, 7 und 11.
• Alle Primzahlen, die beim Teilen durch 4 in den Rest 1 lassen, sind nicht mehr prim in , sondern bekommen dort interessante zusätzliche Teiler. Das liegt daran, dass diese Zahlen sich als Summe von zwei Quadraten schreiben lassen.

Streng genommen geht es hier nicht um die Eigenschaft, prim zu sein, sondern um die Eigenschaft, irreduzibel zu sein (siehe oben). Aber im Ring der Ganzen Gaussschen Zahlen fallen diese Begriffe zusammen. Wer sich dafür interessiert, findet beispielsweise beim Suchen mit den Stichworten Zwei-Quadrate-Satz von Fermat und Normfunktion bei den Ganzen Gaußschen Zahlen viele weitere Informationen und Details.

Für die Herleitung von effektiven Verfahren, die Primzahlen herausfischen (Primzahlsieb), ist es mitunter nützlich, auf bestimmte Eigenschaften von Primzahlen zurückzugreifen, statt stur alle Teiler zu probieren – von denen gibt es schon für mittelgroße Zahlen nämlich ganz schön viele und es wird selbst mit Hilfe schneller Computer recht zäh. Eine solche Eigenschaft ist im kleinen Satz von Fermat formuliert:

• Ist p eine Primzahl und ist a eine ganze Zahl, so gilt: und a haben beim Teilen durch p den gleichen Rest.

Falls a nicht durch p teilbar ist, dann gibt es noch eine andere Version:

• hat beim Teilen durch p genau den Rest 1.

Dies kann man zur Erkennung von Primzahlen ausnutzen:

• Ist n eine natürliche Zahl, die man auf Primalität untersuchen möchte, so wählt man sich zufällig eine Zahl a, die echt zwischen 1 und n liegt und die teilerfremd zu n ist (falls das nicht möglich ist, dann ist n=2 und man kann den Test sofort beenden).

Nun haben wir also a und n und berechnen . Falls beim Teilen durch n dann der Rest 1 herauskommt, dann ist das Testergebnis "n ist wahrscheinlich prim.".
Andernfalls ist das Testergebnis "n ist zusammengesetzt."

Das Ergebnis "zusammengesetzt" ist immer richtig, aber das Ergebnis "prim" ist manchmal falsch. Bei den sogenannten Pseudoprimzahlen erscheint für manche Werte von a die Ausgabe "prim", obwohl die Zahl in Wirklichkeit zusammengesetzt ist. Noch schlimmer: Bei den sogenannten Carmichael-Zahlen ist es sogar so, dass für jede mögliche Zahl a, die man sich für den Test wählen könnte (mit den Einschränkungen von oben), der Test das Ergebnis "prim" ausgibt, obwohl die Zahl in Wirklichkeit zusammengesetzt ist.

Solche "Unfälle" haben dazu geführt, dass man nach feineren Tests gesucht hat, die weniger Fehler machen. Ein Beispiel ist der Miller-Rabin-Test. Der erste Schritt ist dabei so ähnlich wie beim Fermat-Test, aber es gibt danach noch einen zweiten Schritt.

Auf der Seite http://www.visual.wegert.com von Elias Wegert findet man viele wunderbare Illustrationen, manche davon haben mit Primzahlen zu tun. Hier sind noch mehr Tipps zum Stoebern und Weiterlesen:

Literatur und weiterführende Informationen

• Chris K. Caldwell: The List of Largest Known Primes Home Page
• R. Waldecker, L. Rempe-Gillen: Primzahltests für Einsteiger, 2. Auflage. Springer, 2015. Auch in englisch erhältlich: Primality testing for beginners, Januar 2014 in der Serie Student Mathematical Library der AMS.
• E. Wegert: Visual Complex Functions, Birkhäuser, 2012.
• Agrawal, M., Kayal, N. und Saxena, K.: PRIMES is in P, Annals of Math. 160 (2004), No. 2, 781 – 793.
• Hardy, G.H.: A mathematician's apology, Cambridge University Press, 1992.
• Crandall, R. und Pomerance, C.: Prime Numbers: A computational perspective, Springer, 2005.
• Dietzfelbinger, M.: Primality Testing in Polynomial Time: from randomized algorithms to PRIMES is in P, Springer, 2004.

Podcasts

• S.Ritterbusch: Digitale Währungen, Gespräch mit G. Thäter im Modellansatz Podcast, Folge 32, Fakultät für Mathematik, Karlsruher Institut für Technologie (KIT), 2014. http://modellansatz.de/digitale-waehrungen
• F. Januszewski: L-Funktionen, Gespräch mit G. Thäter im Modellansatz Podcast, Folge 55, Fakultät für Mathematik, Karlsruher Institut für Technologie (KIT), 2015. http://modellansatz.de/l-funktionen
• F. Schmidt: RSA-Faktorisierung, Gespräch mit G. Thäter im Modellansatz Podcast, Folge 70, Fakultät für Mathematik, Karlsruher Institut für Technologie (KIT), 2015. http://modellansatz.de/rsa-faktorisierung