Das
GIMPS-Projekt vermeldet die Entdeckung der 43. Mersenne-Primzahl und damit der bisher größten bekannten Primzahl. Die Zahl wird jetzt nochmal überprüft und dann in wenigen Tagen veröffentlicht.
Was ich heute zum Anlaß nehme, ein bißchen was über Primzahlen zu erzählen, weil ich das ein unheimlich spannendes Thema finde.
Einführung für Nicht-Mathematiker
Eine Primzahl ist eine natürliche Zahl, welche exakt zwei Teiler besitzt, die 1 und sich selbst. Primzahlen sind etwa 2, 3, 5, 7, 11, 13, ...
Relevanz von Primzahlen
Die größte Relevanz haben Primzahlen in der Public-Key-Kryptographie - so basiert etwa das weitverbreitete RSA-Verfahren auf der Tatsache, dass es einfach ist, zwei große Primzahlen miteinander zu multiplizieren, jedoch nur mit großen Rechenaufwand möglich, das Ergebnis wieder in seine Primzahlen zu zerlegen.
Die Kryptographie und die damit verbundene Zahlentheorie sind ein Beispiel für eine Wissenschaft, die lange Zeit aus rein theoretischen Erwägungen durchgeführt wurde und dann aufgrund der technischen Entwicklung plötzlich zu großer Relevanz führte.
Primzahlen erkennen
Ein bis vor wenigen Jahren ungelöstes Rätsel war es, ob ein ein effizienter (mathematisch: polynomialen) Algorithmus existiert, welcher eine Primzahl erkennt. Lange Zeit wurden hierfür lediglich Näherungsverfahren angewendet, die lediglich mit sehr hoher Warscheinlichkeit feststellen, ob eine Zahl prim ist. Erst 2001 gelang es drei indischen Wissenschaftlern mit dem AKS-Test einen solchen Algorithmus zu entwickeln.
Illegale Primzahl
Die
erste bekannte Primzahl, die nach dem amerikanischen DMCA (inzwischen auch in der EU) illegal ist, enthält den Code des DVD-Entschlüsselungstools DeCSS.
Ungelöste Primzahl-Probleme
Die Beschäftigung mit Primzahlen bietet Perspektiven - es gibt eine ganze Reihe ungelöster Primzahl-Probleme:
Große Primzahlen: Die oben angesprochenen Mersenne-Primzahlen sind bislang die effizienteste Methode, extrem große Primzahlen (mit mehreren tausend Stellen) zu erzeugen. Dabei handelt es sich um Zahlen der Form 2^n-1. Obwohl es sehr leicht möglich ist, mit dem Euklidschen Primzahlbeweis zu zeigen, dass es unendlich viele und damit unendlich große Primzahlen gibt, gibt es bislang keine Methode, aus dem Euklidschen Beweis ein einfaches Verfahren zur Erzeugung beliebig großer Primzahlen zu entwickeln. Ein solches würde einem auch gleich die diversen Preise der
EFF für die Entdeckung großer Primzahlen bescheren.
Primzahl-Zwillinge: Es ist bislang nicht bekannt, ob es unendlich viele Primzahl-Zwillinge gibt. Primzahl-Zwillinge sind zwei Primzahlen, die sich lediglich um 2 unterscheiden, also etwa 3 und 5, 11 und 13 etc. Daran schließt sich die Frage an, ob es unendlich viele Primzahlvierlinge, d. h. Primzahlen der Form n, n+2, n+6, n+8 gibt (beispielsweise 5, 7, 11, 13). Lässt sich natürlich beliebig fortsetzen.
Schneller Primzahltest: Zwar existiert mit dem AKS-Algorithmus ein polynomialer Algorithmus zur Bestimmung von Primzahlen, jedoch ist dieser noch sehr langsam - in allen praktischen Anwendungen, etwa in der Kryptographie, werden weiterhin Näherungsverfahren angewandt. Eine Optimierung des AKS-Algorithmus oder ein neuartiger Algorithmus, der auch in praktischen Anwendungen (Zahlen bis 4096 Bit) schnell ist, wäre hier eine spannende Entdeckung.
Goldbachsche Vermutung: Lässt sich jede Gerade Zahl größer 2 als Summe aus zwei Primzahlen darstellen (2+2=4, 3+3=6, 3+5=8, 3+7=10 etc.)? Funktioniert für alle getesteten Zahlenräume, indes, der Beweis fehlt, obwohl es so einfach aussieht.
Faktorisierung: Die wohl spannendste Frage, gibt es eine Möglichkeit, große Zahlen effizient in ihre Primfaktoren zu zerlegen? Ein solches würde fast die gesamte heute angewandte Kryotpgraphie unbrauchbar machen. Man geht heute davon aus, dass Primzahlen bis 1024 Bit mit großen finanziellen Aufwand brechbar sind (nach Twirl googeln oder mal den Wikipedia-Artikel dafür schreiben). Die Firma
RSA-Security zahlt Preisgelder für die Faktorisierung großer Zahlen - die Zahl RSA-640 (steht für die Bit-Zahl) wurde bereits faktorisiert, als nächstes steht RSA-704 an. Das Thema wurde bereits in mehreren Filmen verarbeitet (Mercury-Puzzle, Sneakers).
Mit einem Quantencomputer wäre eine effiziente Faktorisierung möglich - mit dem SHOR-Algorithmus - ein solcher Quantencomputer existiert jedoch bislang nur in der Theorie.
Wikipedia
hat noch ein paar Probleme parat. An einem anderen Problem war ich auch schonmal dran (hat aber nix mit Primzahlen zu tun), aber welches verrat ich jetzt nicht - sonst nimmt es mir noch jemand weg ;-)
Etwas, wozu ich bei kurzer Recherche keine verifizierbaren Infos gefunden hab: Es gibt immer wieder Berichte von Fällen, in denen Autisten mit großer Geschwindigkeit Primzahlen erkennen konnten - ebenfalls in einigen Filmen verwandt (The Cube, Rainman). Urban-Legend oder gibt's dazu wissenschaftliche Ergebnisse?
Ich hoffe alles war soweit inhaltlich richtig, Mathematiker mögen mich korrigieren.
Zu guter letzt ein Zitat aus dem heise-Forum. Ein Teilnehmer fragte
kann man mit dieser zahl jetzt irgendwas sinnvolles anfangen?
woraufhin ein anderer antwortete
Kann man mit der Fußball-WM irgendwas sinnvolles anfangen?
Genau!
