Mathematik: Primzahlen in Kryptologie und Biologie

Primzahlen sind alle von 1 verschiedenen und nur durch 1 und sich selbst teilbaren natürlichen Zahlen. Alle anderen natürlichen Zahlen (mit Ausnahme von 1) sind als ein Produkt von Primzahlen darstellbar. Die Untersuchung der Primzahlen geht auf die alten Griechen zurück. Die Schule des Pythagoras (um 570 – 500), die etwa zwischen 500 und 300 v. Chr. blühte, interessierte sich besonders für sie. Euklid (um 365 bis um 300) gelang es dann, nachzuweisen, dass es unendlich viele Primzahlen geben muss. Er vermutete auch, dass jede ganze Zahl n in der Formel 2ⁿ – 1 zu einer Primzahl führt.

Das "Sieb des Eratosthenes" (etwa 290 – 214) schließlich war der erste, wenn auch noch sehr einfache Algorithmus zum Berechnen einer Primzahl. Aus einer unendlich langen Liste natürlicher Zahlen werden zuerst alle Vielfachen der kleinsten Primzahl 2 entfernt. Diese Prozedur wird dann mit der 3, der 5, der 7 usw. wiederholt.

Mersennesche und Fermatsche Primzahlen

Weder die Römer noch die Denker des Mittelalters befassten sich mit diesem Phänomen. Wichtige Vertreter der Zahlentheorie der Neuzeit waren die französischen Mathematiker Marin Mersenne (1588 – 1648) und Pierre de Fermat (1601 – 1665). Der Paulanermönch Mersenne hatte behauptet, alle Zahlen der Formel 2ⁿ – 1 seien dann Primzahlen, wenn n selbst eine Primzahl und nicht größer als 257 ist. Danach ist z. B. 2¹³ – 1 = 8192 – 1 = 8191 eine Primzahl und ist bereits 1456, also lange vor Mersenne, von einem unbekannten Mathematiker als solche nachgewiesen worden. Fermat, Leonhard Euler (1707 – 1783) und andere zeigten jedoch, dass die Mersennesche Regel nicht in allen Fällen zutrifft. Eine solche Ausnahme bildet die von Francois Lucas (1842 – 1891) 1876 nachgewiesene Primzahl 2¹²⁷ – 1 = 170 141 183 460 469 231 731 687 303 715 884 105 727.

Erst 1947 gelang es, die Fehler von Mersennes Behauptung auszumerzen. Dennoch spricht man bis heute von Mersenneschen Primzahlen, wenn sie der Regel M_n = 2ⁿ – 1 gehorchen. Da sich die Regel sehr einfach überprüfen lässt, liefern alle modernen Rekorde Mersennesche Primzahlen.

Fermat, der Mersenne gut gekannt hat und sich sehr intensiv mit der Zahlentheorie beschäftigte, erstellte eine eigene Formel für Primzahlen (p): p = 2ⁿ + 1 wobei n eine Potenz von 2 sein muss: n = 2^k. Für k = 0, 1, 2, 3 und 4 ergeben sich die Primzahlen 3, 5, 17, 257 und 65 537. Bis heute ist allerdings keine weitere Fermatsche Primzahl gefunden worden. Darüber hinaus gibt es weitere Verfahren zum Finden von Primzahlen.

Immer neue Rekorde

Das Computerzeitalter brachte nur wenig Fortschritt auf dem Gebiet der Zahlentheorie, dafür umso mehr Primzahlrekorde. Der erste, der einen elektronischen Rechner zur Suche der größten Primzahl nutzte, war ein US-Amerikaner namens Robinson. Er fand 1952 die damals größte Primzahl M₂₂₈₁.

Es gibt bis heute keine Regel, schnell beliebig große Primzahlen zu berechnen. Deshalb ist der Ehrgeiz, neue Rekorde aufzustellen, nur natürlich. Aktuell liegt er bei M_6972593. Doch wozu das Ganze?

Verschlüsselung mithilfe von Primzahlen

Schon Caesar verschlüsselte seine Botschaften, als er mit Pompejus und Crassus aus dem Exil sein erstes Triumvirat vorbereitete. Der Trick war damals noch sehr einfach. Die Buchstaben der geheimen Texte wurden ein paar Stellen im Alphabet weitergerückt. Das war eine einfache Verschiebechiffre; der Schlüssel ist das festgelegte Verschiebungsintervall.

Heute sind Primzahlen die notwendige Grundlage elektronischer Schlüssel. Denn sie sind als Zahlen eindeutig definiert, nicht mehr in kleinere Faktoren zerlegbar. Die Entschlüsselung ist komplizierter als bei den alten Römern, wie ein (relativ) einfaches Beispiel verdeutlicht:

Die von einem Geheimniskrämer übermittelte Botschaft lautet: 472, 1072, 143, 872, 380. Der dazugehörige Schlüssel ist (51, 3). Die erste Zahl des Schlüssels ist der Hauptmodul, die zweite Zahl der Verschlüsselungsexponent. Um die Chiffren der Botschaft in Buchstaben umsetzen zu können, müssen zuvor noch der Nebenmodul und der Entschlüsselungsexponent errechnet werden.

Zuerst der Nebenmodul: Der Hauptmodul 51 lässt sich in die beiden Primzahlfaktoren 3 und 17 zerlegen: 51 = 3 x 17. Von diesen Primzahlen wird jeweils 1 subtrahiert, dann werden die Differenzen miteinander multipliziert und ergeben den Nebenmodul: (3 – 1) x (17 – 1) = 2 x 16 = 32.

Nun der Entschlüsselungsexponent: Er ist die Zahl, die den Rest 1 ergibt, wenn sie mit dem Verschlüsselungsexponenten multipliziert und anschließend durch den Nebenmodul dividiert wird. Dieser Entschlüsselungsexponent wird mühsam gesucht. Im Beispiel ergibt sich die 11. Denn 3 x 11 = 33. Und 33 : 32 = 1, Rest 1. Wir kennen nun: Hauptmodul: 51 Nebenmodul: 32 Verschlüsselungsexponent: 3 Entschlüsselungsexponent: 11

Um die erste Chiffre zu identifizieren, sind mehrere Rechenoperationen nötig: Zuerst dividiert man sie durch den Hauptmodul: 472 : 51 = 9, Rest 13

Den Rest potenziert man mit dem Entschlüsselungsexponenten: 1311 = 1 792 160 394 037

Das Ergebnis dividiert man durch den Hauptmodul, wobei man den Rest ignoriert: 1 792 160 394 037 : 51 = 35 140 399 883

Den Quotienten multipliziert man wieder mit dem Hauptmodul: 35 140 399 883 x 51 = 1 792 160 394 033

Dieses Produkt subtrahiert man von der oben ausgerechneten Zahl 1311. Die Differenz ist das gesuchte Endergebnis: 1 792 160 394 037 – 1 792 160 394 033 = 4

Damit steht der erste Buchstabe der Botschaft fest; es ist das D, der 4. Buchstabe des Alphabetes. Das Lösungswort ergibt sich aus der Berechnung jeder einzelnen Chiffre nach diesem Schema. Die Chiffren 1072, 143, 872 und 380 werden zu den Buchstaben A, N, K und E.

Die Größe entscheidet ...

Carl Friedrich Gauß (1777 bis 1855) sagte, "dass die Aufgabe, die Primzahlen von den zusammengesetzten zu unterscheiden und letztere in Primfaktoren zu zerlegen, zu den wichtigsten und nützlichsten der gesamten Arithmetik gehört", und er wusste, dass die Methoden "mühsam und aufwendig" sind. Doch für moderne Computer stellt das Rechnen mit großen Zahlen kein Problem dar.

Die Hürde beim Enträtseln eines Codes ist die Zerlegung des Hauptmoduls in seine Primfaktoren. Bei der Zahl 51 kann das fast jeder Schüler. Mit schnellen Rechnern lassen sich heute in Minutenschnelle 100-stellige Primzahlen p und q erzeugen. Doch für die Zerlegung ihres 200-stelligen Produktes m = pq in die Ausgangsfaktoren p und q benötigen die besten Computer theoretisch eine Milliarde Jahre. Schon ab 40 Dezimalstellen ist der Rechenaufwand enorm.

Mittels einer ausgeklügelten Variante eines hier nicht erklärbaren Faktorisierungsprinzips ist es kürzlich gelungen, eine 129-stellige Dezimalzahl zu faktorisieren, d. h. zu zerlegen, die das Produkt zweier großer Primzahlen darstellt. Dies dauerte rund acht Monate und erforderte den Zusammenschluss von weltweit 600 Rechnern. Das Ergebnis: 114 381 625 757 888 867 669 235 779 976 146 612 010 218 296 721 242 362 562 561 842 935 706 935 245 733 897 830 597 123 563 958 705 058 989 075 147 599 290 026 879 543 541 = 3 490 529 510 847 650 949 147 849 619 903 898 133 417 764 638 493 387 843 990 820 577 x 32 769 132 993 266 709 549 961 988 190 834 461 413 177 642 967 992 942 539 798 288 533

... über den Zeitaufwand

Wie schwierig das ist, zeigt auch eine Meldung vom Februar 2002. Mathematikern der Universität Bonn war es gelungen, eine Zahl mit 158 Stellen in ihre Primfaktoren zu zerlegen. Das ist der aktuelle Weltrekord. Der bisherige Rekord von 1999 lag bei 155 Stellen, und das aus einem einzigen Grund. Die internationale Forschergruppe hatte einen Hochleistungsrechner mit 512-stelligen Binärzahlen verwendet. Das entspricht genau 155 Stellen im Dezimalsystem. Die Forscher um Professor Jens Franke in Bonn nutzten dagegen vernetzte handelsübliche Rechner.

Seit etwa 20 Jahren hat sich die Kryptologie aus einer militärischen zu einer eigenständigen zivilen Forschung weiterentwickelt, die alle sicherheitsrelevanten Dinge des Lebens verschlüsselt, vom Mobilfunk bis zur Geldkarte. Die auf Großrechnern erzielten Rekorde haben mit der allgemeinen Schlüssellänge nichts zu tun. Das moderne IDEA-Verfahren (International Data Encryption Algorithm) beruht auf 128 Bit, ist also von den oben angegebenen 512 Bit noch weit entfernt. Dennoch sind gegen IDEA noch keine erfolgversprechenden kryptologischen Attacken bekannt geworden.

Das vor allem beim Versenden von E-Mails weit verbreitete Public-Domain-Chiffrierprogramm PGP (Pretty Good Privacy) beruht auf IDEA zur Datenverschlüsselung und nutzt RSA, nach dem das obige Beispiel gerechnet ist, zur Schlüsselverwaltung (RSA ist nach seinen Erfindern Rivest, Shamir und Adleman benannt). Es gilt als so sicher, dass es nicht nur den Geheimdiensten Kopfzerbrechen bereitet, sondern auch z. B. für Chipkarten benutzt wird. Die Zahlentheorie steckt heute also in jedem Geldbeutel.

Goldbachs Vermutung

Die Primzahlforschung ist noch lange nicht zu Ende. Rund 25 Prozent der Zahlen zwischen 1 und 100 sind Primzahlen, 17 Prozent sind es zwischen 1 und 1000. Je größer die Zahlen, umso seltener werden die Primzahlen. Zwischen 1 und 1 000 000 findet man nur noch zu 7 Prozent Primzahlen. Adrien-Marie Legendre (1752 – 1833) und Gauß vermuteten für sehr große Zahlen n, dass es n/logn Primzahlen gibt. Das wurde später bestätigt.

Die Verteilung der Primzahlen ist noch nicht verstanden. Sie scheint dennoch einem Gesetz zu folgen. Es existieren große Lücken, und dann taucht wieder das rätselhafte Phänomen der sehr großer Primzahlzwillinge auf, die wie 5 und 7 um den Wert 2 auseinander liegen. Vermutlich gibt es unendlich viele davon. Doch das ist unbewiesen.

Der britische Verlag Faber and Faber hat nun zur werblichen Unterstützung eines Romans 1 Million US-Dollar ausgelobt für denjenigen, der Goldbachs Vermutung beweist. Der preußische Mathematiker Christian Goldbach hatte 1742 in einem Brief an Leonhard Euler in Berlin vermutet, dass jede gerade Zahl größer als 4 als Summe zweier Primzahlen ausgedrückt werden könne. Alle Mathematiker haben sich bisher daran die Zähne ausgebissen.

1998 hatte Jörg Richstein von der Universität Gießen die geraden Zahlen bis 400 Billionen untersucht und kein Gegenbeispiel gefunden. Doch das ist kein mathematischer Beweis. Deutsche brauchen sich aber gar nicht erst um den Preis zu bemühen. Es sind nur Briten und Amerikaner zugelassen.

Forschung mit Zikaden

1634 erschreckte eine furchtbare Zikadenplage die ersten europäischen Siedler im Osten Tennessees. Seitdem wiederholt sich diese Plage mit absoluter Regelmäßigkeit alle 17 Jahre. Fast auf die Woche genau kriechen die hemimetabolen Insekten aus dem Boden, entwickeln und paaren sich und sterben wenige Wochen später nach der Eiablage. In einer benachbarten Region vollzieht sich dieses Schauspiel alle 13 Jahre.

Mit dieser Entdeckung haben die Primzahlen ihren Einzug in die Biologie gehalten. Die Periode versucht man mit Jäger-Beute-Zyklen zu erklären. Bei einer zwölfjährigen Zykluslänge fielen die Beutetiere allen Räubern mit Zyklen von 1, 2, 3, 4, 6 und 12 Jahren zum Opfer. Am Max-Planck-Institut für molekulare Physiologie wurde jetzt ein Evolutionsmodell entwickelt, das durch Mutation und Selektion von Räubern und Beuten Primzyklen der Beuten erzeugt. Mario Markus und Oliver Schulz konnten zeigen, dass Perioden in Primzahllänge stabil gegen zyklenveränderte Mutationen sind. Ein Problem des Modells ist jedoch, dass der Räuber der Zikaden noch nicht gefunden wurde.

Kasten: Surftipp

www.cryptool.de Ein freies Programm der Deutschen Bank zum Ausprobieren kryptographischer Verfahren. Es erzeugt Hauptmodule beeindruckender Länge, Schlüssel und vieles mehr.