Primzahlen und Gruppen

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.

In der Vergangenheit gab es verschiedene Definitionen für
Primzahlen, die sich über die Zeit zu dem heute gebräuchlichen
geschärft haben:


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:
Wie viele Primzahlen gibt es? Gibt es beliebig große
Primzahlzwillinge, d.h. zwei Primzahlen, die voneinander nur den
Abstand 2 haben (wie z.B. 11 und 13)? Wie kann ich eine Zahl als
Primzahl erkennen? 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