Science - 2

Vor circa einem halben Jahr hab ich Lars am Telefon erzählt, dass ich glaube, die katholische Kirche wird demnächst wieder zum Kreationismus zurückfallen. Er meinte damals, ich soll das bloggen, damit ich nachher behaupte kann, ich hätte es vorher gewußt.
Hab ich leider nicht gemacht. Der Guardian berichtet über Bestrebungen im Papst-Umfeld, sich die Intelligend Design-Theorie zu eigen zu machen (Intelligent Design ist letztendlich nichts anderes als die pseudowissenschaftliche Verpackung für Kreationismus).

Ich halte es ja nach wie vor mit dem fliegenden Spaghettimonster.

Found in the net, made me laugh:
PETA sues FermiLab for cruelty to Schrödinger's Cat; outcome uncertain
(from mplayer mailinglist)

From todays solar eclipse, which could be partially watched from Germany, I tried to take some pictures.

Good that I kept my special eclipse sun glasses from 1999 (when we had a total eclipse over south Germany I completely missed due to the bad weather back then). Most of the time it was cloudy, but I still managed to get some nice pics.

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!

Meistens les ich ja telepolis ganz gerne. Nur gelegentlich kommt völliger Bullshit dabei heraus. So schwadroniert heute ein Artikel, dass asymmetrische Kryptografie bald obsolet werden könnte.

Kleine Einführung für nicht-Mathematiker: Bei fast allen sicheren Online-Verbindungen wie ssl, ssh o.ä., sowie bei eMail-Verschlüsselung mit PGP/GnuPG und in vielen weiteren Fällen wird sogenannte asymmetrische Kryptografie (auch Public Key-Verfahren genannt) eingesetzt. Das bekannteste und am weitesten verbreitete Verfahren ist RSA, die meisten anderen Verfahren (El Gamal, DSA) basieren auf ähnlichen mathematischen Problemen.

Die Sicherheit von RSA beruht darauf, dass es zwar einfach ist, zwei große Primzahlen miteinander zu multiplizieren, umgekehrt jedoch schwierig, eine Zahl in ihre Primfaktoren zu zerlegen. Hat man also beispielsweise zwei große Primzahlen a und b, so ist es einfach a*b=c zu berechnen. Umgekehrt ist es jedoch nur mit hohem Rechenaufwand möglich, von c auf a und b zu schließen.

2001 haben drei Inder den AKS-Test entwickelt, mit dem man in polynomialer Rechenzeit (einfach gesprochen heißt das: auch bei großen Zahlen noch schnell) herausfinden kann, ob eine große Zahl eine Primzahl ist oder nicht. Für die Sicherheit von RSA ist dies jedoch völlig unbedeutend. Im Gegenteil: Um RSA nutzen zu können, benötigt man schnelle Primzahltests bei der Schlüsselgenerierung. Es ist mathematisch gesehen ein völlig anderes Problem, eine Zahl zu faktorisieren oder sie auf ihre Primzahleigenschaft zu testen.

Nun ist das schon einige Jahre her und war auch damals nicht wirklich überraschend. Das einzige, was passiert ist: Der bekannte AKS-Test wurde in einer mathematischen Zeitschrift veröffentlicht. Genaugenommen ist also garnichts passiert.

Übrigens gibt es bereits seit den 70er-Jahren den sogenannten Miller-Rabin-Test, von dem man ebenfalls vermutet, dass er in polynomialer Zeit Primzahlen erkennen kann. Dafür fehlt bislang jedoch der Beweis. Überraschen konnte das Ergebnis der drei Inder daher aber auch 2001 nicht wirklich.

Korrekt ist im übrigen, dass es rein theoretisch möglich wäre, dass ein bisher unbekannter Algorithmus zur schnellen Faktorisierung existiert. Nur hat ihn bisher noch niemand gefunden (und da sich mit diesem Problem Mathematiker schon ziemlich lange rumschlagen, ist damit auch nicht in absehbarer Zeit zu rechnen).

Daneben strotzt der Artikel nur so von inhaltlichen Fehlern. So wird behauptet, die Faktorisierung von Zahlen sei nur in exponentieller Rechenzeit möglich. Mit modernen Verfahren, etwa dem Zahlkörpersieb, ist dies deutlich schneller möglich, nur eben immer noch zu langsam, um RSA mit ausreichend großer Schlüssellänge (>=2048 bit) in annehmbarer Zeit zu brechen.

Kleiner Tipp an telepolis: Wenn ihr das nächste Mal etwas über Kryptografie schreibt, sucht doch erstmal jemand, der zumindest mal eine Anfängervorlesung dazu besucht hat. Dann würdet ihr vielleicht nicht so einen Unfug schreiben.

Quellen:
Vorlesungsskript über den AKS-Algorithmus (war selber in der Vorlesung)
Miller-Rabin-Test bei Wikipedia
AKS-Test bei Wikipedia

Gerade hier gefunden (ham die bei Twoday keine Trackbacks??):
Eine handgeblasene kleinsche Flasche kann man da bestellen.

Betrieben wird das ganze von Clifford Stoll, dem Autor des Buches Kuckucksei (welches ich zufällig kürzlich gelesen habe). Leider sind mir die Teile dann doch etwas zu teuer.

Zu den vor einiger Zeit hier vorgestellten Gedanken zu überabzählbaren Zahlenmengen habe ich zufällig eine brauchbare Antwort gefunden (im Buch "Computerdenken" von Roger Penrose).

Man spricht bei den von mir benannten Zahlen, die sich durch einen Algorithmus (den man auf ein endliches Blatt aufschreiben kann), von berechenbaren reellen Zahlen, während es im Gegensatz dazu auch nicht berechenbare reelle Zahlen gibt, also solche, für die kein Algorithmus (bspw. eine Turingmaschine) existiert, der die Zahl (oder deren n-te Stelle) ausgibt. Es gibt also mathematisch gesehen durchaus Zahlen, die zwar irgendwie existieren, für deren Berechnung man aber keinerlei Rechenvorschrift angeben kann.

Grad angekommen ist hier eine Bestellung (bei einem großen online-Buchladen, den ich eigentlich boykottiere, aber lassen wir das) eines Buches mit dem Namen "Computerdenken" von Roger Penrose.
Vor einiger Zeit hab ich ja den Artikel Gedanken zum menschlichen Bewußtsein geschrieben. Da ich mich gern weiter mit ähnlichen Themen beschäftigen wollte, bin ich auf das Buch gestoßen. Der Autor versucht wohl, über Quantentheorie, Mathematik (Hilbert, Turing, Gödel), Chaostheorie, ... seine Thesen zur künstlichen Intelligenz darzustellen.
Klingt auf jeden Fall mal spannend und wenn ich durch bin, werd ich hier eine kleine Rezension schreiben.

Grad zurück vom jährlichen Kongress des Chaos Computer Clubs, ein bißchen ausgeschlafen (naja, ausschlafen + Kaffee ;-), gibt's hier mal so ne Art Mini-Report.
Wie letztes Jahr schon fand der Kongress im BCC am Alexanderplatz statt, diesmal leider ohne großen Bildschirm im Nebenhaus.
Ein spannendes Vortragsprogramm und natürlich viel zu wenig Zeit, alle zu besuchen, mit allen Bekannten zu quatschen und gleichzeitig alles auf dem Kongress zu sehen (und noch Schlaf gelegentlich nachzuholen).
Einige Vortragshighlights picke ich mal raus, viele, die ich verpasst hab, will ich mir noch als Streams reinziehen.
Im Vortrag über die Urheberrechtsnovelle wurden die ganzen Gruseligkeiten, die der zweite Korb hier mit sich bringt, aufgerollt und für die Fairshare-Kampagne geworben. Überhaupt waren die Aktivisten hier sehr präsent und ham's sogar in die tagesschau geschafft. Ich bin zwar persönlich nicht unbedingt mit allen Zielen dieser Kampagne einverstanden, halte sie aber für einen guten Ansatz, das Thema mal von der anderen Seite ins Gespräch zu bringen.
Im Vortrag über TCPA stellte Rüdiger Weiss in seiner gewohnt witzigen Art (eigentlich hätte der vielleicht Komiker statt Mathematiker werden sollen - wobei, dann hätten wir keine so schönen Vorträge von ihm) den aktuellen Stand dar und erhielt großen Applaus für seine Aussage, dass, nachdem schon viele Jugendliche durch den Konsum verbotener Substanzen sinnlos kriminalisiert werden, nicht das gleiche mit Filesharern gemacht werden sollte.
In zwei Vorträgen über "Quantentheorie für nicht-Physiker" (genau das richtige für mich als Physik-Nebenfach-Student ;-) durfte ich auch noch einiges dazulernen über die Zusammenhänge zwischen Welle-Teilchen-Dualismus, den komischen Mustern hinter Doppelspalten (jaja, eigentlich hatte ich das ja schon im Abi) und vieles mehr.
Am dritten Tag gab's den von mir besonders gespannt erwarteten Vortrag zu MD5, der Referent stellte live einen Angriff gegen das HASH-System von Kazaa vor. Was mir leider gefehlt hat, ist ein Ausblick auf HASH-Funktionen im allgemeinen und wie die ebenfalls bekannten Schwächen in SHA-1 zu bewerten sind.
Zum Abschluss gab's mal wieder Security Nightmares, von OS/2-Bankomaten mit Kommandozeile, rebootende Autos und U-Bahnen, sowie weggekommene Datenbanken des CCCs war für jeden was zum Lachen dabei.

Was etwas unschön war, dass es wie im Vorjahr schon etwas wenig Platz zum Hinsetzen für nicht-Projektleute gab und dass der Rauch in den Gängen, sowie das häufige nichtbeachten der Nichtraucherzonen die Luftqualität doch stark beeinträchtigt hat. Hier wäre vielleicht eine sinnvollere Einteilung (Raucher-Zonen so, dass nicht jeder ständig durch muss) empfehlenswert. Und eine kleine Kritik am Essensangebot, zeitweise war kein vegetarisches Essen verfügbar. Aber das war verschmerzbar, der Alexanderplatz mit reichhaltiger Auswahl war ja nicht weit.

Alles in allem ein lohnender Trip und nächstes Jahr sicher wieder.

(P.S.: so viele Kategorien hab ich beim bloggen noch nie angekreuzt - ein Zeichen, wie vielfältig der Kongress war)

Mathematische Paradoxen gibt es viele, bekannt ist etwa das Barbier-Paradoxon, welches davon erzählt, dass ein Barbier ein Schild an seiner Tür hatte, auf dem Stand
"Ich rasiere genau die, die sich nicht selbst rasieren."
bis ihn einmal sein Sohn fragte, ob er sich eigentlich selbst rasierte. Man merkt schnell, dass man sich in einen Widerspruch verstrickt, da wenn er sich selbst rasiert, würde er sich ja nach seiner eigenen Aussage nicht selbst rasieren. Der Barbier musste sich wohl einen Bart wachsen lassen, für die Mathematiker ergaben sich daraus aber größere Probleme, die letztendlich zu Gödels Unvollständigkeitssatz und Turings Halteproblem (siehe dazu auch "Gedanken zum menschlichen Bewußtsein, der dort verlinkte Vortrag beschäftigt sich ebenfalls mit diesen Paradoxen).
Ein etwas mathematischeres Beispiel für ein Paradoxon ist folgendes:
Definitiere: X ist die kleinste Zahl, die sich nicht mit weniger als tausend Worten beschreiben lässt.
Nun, wir merken schnell: Wir haben X gerade mit 16 Worten beschrieben. Damit ist X mit weniger als tausend Worten beschreibbar.

Ich möchte hier eine Überlegung ausführen, die ich selber hatte und die ich bisher mit keinem Mathematiker diskutiert habe. Falls unter den Lesern meines Blogs ein Mathematiker ist, der was dazu sagen kann, würde ich mich über Kommentare freuen. Die Überlegung sollte von jedem, der sich etwas für Mathematik interessiert, nachvollziehbar sein, auch ohne Mathe-Studium. Ich setze lediglich voraus, dass man mit den Begriffen natürliche und reelle Zahlen etwas anfangen kann. Die Mathematiker bitte ich, mir zu verzeihen, dass ich teilweise unscharf argumentiere, aber der Grundgedanke dürfte auf jeden Fall klar werden.

Abzählbar und Überabzählbar

Zunächst muss ich eine kleine Einführung in die Theorie unendlicher Zahlen geben, Mathematiker und sonstige Menschen, die mit den Begrifflichkeiten bereits vertraut sind, dürfen getrost überspringen.
Es gibt in der Mathematik unterschiedliche Arten von unendlich. Während etwa die natürlichen Zahlen (1, 2, 3, ...) abzählbar sind, sind die reellen Zahlen dies nicht. Abzählbar ist eine Menge genau dann, wenn es eine bijektive Abbildung auf die natürlichen Zahlen gibt oder (etwas weniger mathematisch) wenn man die Zahlen in eine Reihenfolge bringen kann.
Es gibt einen relativ leicht nachvollziehbaren Beweis von Cantor, warum die reellen Zahlen nicht abzählbar sind. Stellt man sich vor, dass man reelen Zahlen in eine Reihenfolge bringen könnte, wäre es möglich, sie untereinanderzuschreiben (auf einem unendlich langen und unendlich breiten Blatt). Nun nimmt man nun die erste Nachkommastelle der ersten Zahl und erhöht sie um 1, bzw., wenn diese 9 ist, macht eine Null daraus. Anschließend nimmt man von der zweiten Zahl die zweite Nachkommastelle und geht genauso vor etc. Aus den so erhaltenen Ziffern erzeugt man eine neue reelle Zahl, die sich zu jeder der aufgeschriebenen Zahlen an mindestens einer Stelle unterscheidet. Da diese neue Zahl in der Abzählung nicht vorkommt, muss sie falsch sein, d.h. die reellen Zahlen sind nicht Abzählbar oder (mathematisch ausgedrückt) Überabzählbar.

Meine Überlegung dazu

Wenn wir uns mal fragen, was die reellen Zahlen eigentlich sind, kommt man darauf, dass bei den reellen Zahlen eigenltich jede beliebige Anordnung von Ziffern möglich ist, wenn man irgendwie mathematisch beschreiben kann, wie sich diese Anordnung zusammensetzt.
Nun, genau da verstrickt man sich aber in einen Widerspruch. Wenn sich jede reelle Zahl irgendwie beschreiben lässt, liese sich diese Beschreibung auf einem (beliebig großen) Blatt Papier aufschreiben. Dieses Blatt Papier können wir uns als Anordnung von Pixeln in Schwarz oder Weiss (meinetwegen auch farbig, die Überlegung gilt analog) vorstellen. Die Geeks wissen natürlich sofort, dass wir es hier mit einer Anordnung von Bits zu tun haben (0 für Schwarz, 1 für Weiss, 2-color-Bitmap, yeah, das waren noch Zeiten). Eine beliebig lange Anordnung von Bits ist aber nichts anderes als eine Binärzahl und somit eine natürliche Zahl. Damit haben wir eine Abbildung auf die natürlichen Zahlen definiert.
Was heißt das nun? Es gibt reelle Zahlen, die sich nicht beschreiben lassen, egal wie viel Platz und wieviel Mathematiker-Hirnschmalz wir haben? Können solche Zahlen existieren?