Science

Second day, finally uploaded some pictures and just found some time to blog between two talks.

Yesterday the We lost the war talk. Maybe I'll write something more in german when I find time for it. In short: IMHO this was an obscure mixture of political nonsense. This should at least be clear when reading the article with similar content in the last »Datenschleuder«, where the author claims something like »till 9.11. hackers ruled the world and everything was good« (to cite, »The big corporations were at our merce, because we knew what the future would look like and we had the technology to built it).
Lars wrote very drastically about it.

Today, the first interesting talk was5 Thesis on Informational-Cognitive Capitalism. I think I didn't really get what the autor wanted to say (surely related to missing sleep and lack of motivation to listen to english), but he was at least quite entertaining.

Next was Hashing Trusted Computing by Rüdiger Weis, as always quite funny, Rüdiger maybe should become the first professional math comedian. The content is obvious, at least for regular readers of my blog: Trusted Computing is evil and SHA1 is broken.

There was a nice presentation by fukami and Markus Beckedahl about the Sony BMG rootkit. They presented a lot of information, Markus has also collected it in his blog.

Next one was Technological art off the trodden tracks by two media artists that presented art which is related to hacking subjects and suggested that media artists and hackers come more together to share thoughts and projects. I hope they'll put their materials online, they had a lot of videos from nice stuff.

Just came from Learning cryptography through handcyphers by Benno de Winter. It was a basic introduction to some simple algorithms, not really new to me, but the speaker was worth watching because of the fun factor.

More to come.

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!