Hallo,

ich hab gerade was über Illegale Primzahl, das sind wohl Primzahlen, die, in binärer Darstellung mit gzip komprimiert, Dokumente, z.B. einen Quelltext ergeben können. Sie müssen natürlich entsprechend viele Stellen haben, ein Beispiel: 1401

Ich versteh das natürlich nicht wirklich! Aber weiß irgendjemand, warum das gerade eine Primzahl sein muss, und nicht irgendeine Zahl? Hat das was mit dem Algorithmus von gzip zu tun?


Moderiert von Narses: Topic aus Algorithmen, Optimierung und Assembler verschoben am Do 10.09.2009 um 09:38

Jakob Schöttl hat folgendes geschrieben :

Hallo, Ich versteh das natürlich nicht wirklich! Aber weiß irgendjemand, warum das gerade eine Primzahl sein muss, und nicht irgendeine Zahl? Hat das was mit dem Algorithmus von gzip zu tun?

Also ich könnt mir vorstellen, dass es halt in dem Fall eine Primzahl ist, weil Primzahlen im Allgemeinen mehr Aufmerksamkeit bekommen als normale Zahlen. Nach Primzahlen wird gesucht, nach normalen Zahlen nicht.
Allerdings, ich hab von dem ganzen jetzt das 1. mal gehört, also wissen tu ich es nicht.

Ehm... die Antwort steht doch bei Wikipedia! Aus rechtlichen Gründen... und da haben die dann getrickst, indem das illegale Programm als Primzahl dargestellt wurde und somit konnte man die "Datei" bzw. die "Ansammlung von 0 und 1" legal vertreiben... Hast du den Text ganz gelesen?!?

platzwart hat folgendes geschrieben :

Ehm... die Antwort steht doch bei Wikipedia! Aus rechtlichen Gründen... und da haben die dann getrickst, indem das illegale Programm als Primzahl dargestellt wurde und somit konnte man die "Datei" bzw. die "Ansammlung von 0 und 1" legal vertreiben... Hast du den Text ganz gelesen?!?

ja so viel hab ich schon mitgekriegt, aber ich hab mich ja gefragt, ob es eben nur Primzahlen gibt, mit denen man sowas machen kann, oder ob das eben zufall ist.

na, dass das Zufall ist, ist irgendwie selbstverständlich. Schließlich hat jede Zahl ein Bitmuster, nicht nur Primzahlen.

nein, da steht, sie haben in der menge der möglichen Zahlen extra nach einer Primzahl gesucht.

Du könntest auch die Zahl Pi nehmen und binär codieren. Irgendwo würdest du die Sources von Windows 7 finden. Wieso Primzahlen, weil man eine normale Zahl nicht mehr finden muss sondern einfach konstruieren könnte. Da hätte man nicht mehr viele Argumente.

Merkwürdich ist doch aber, das ausgerechnet eine Primzahl -mit gzip dekodiert- den Quelltext von DeCSS ergibt. Ich meine, es gibt doch verdammt viele Zahlen und im Vergleich dazu ziemlich wenig Primzahlen, vor allem 1401-Stellige.

Auf der anderen Seite gibt es ja nicht nur einen Quellcode von DeCSS, sondern beliebig viele. Wenn ich diese also komprimiere, bekomme ich auch beliebig viele Bitmuster, a.k.a lange Zahlen. Ist lustig, das dabei eine Primzahl ist, aber -nun ja-, da hat halt jemand zu viel Zeit gehabt und lange gesucht. Oder Glück gehabt.

Mit Sicherheit funktioniert das Ganze auch mit RAR.

Moin!

Ist schon wieder April?

cu
Narses

alzaimar hat folgendes geschrieben :

Merkwürdich ist doch aber, das ausgerechnet eine Primzahl -mit gzip dekodiert- den Quelltext von DeCSS ergibt. Ich meine, es gibt doch verdammt viele Zahlen und im Vergleich dazu ziemlich wenig Primzahlen, vor allem 1401-Stellige.

"ziemlich wenig Primzahlen" ist aber ziemlich relativ , denn es sind ja immerhin ca 2.8E1397. Der relative Anteil der Primzahlen ist in diesen Dimension also ca 1/3600.

Zitat:

Merkwürdich ist doch aber, das ausgerechnet eine Primzahl -mit gzip dekodiert- den Quelltext von DeCSS ergibt.

Ich glaube du interpretierst da zuviel rein.
Ich vermute das der Alghorithmus von zip so ausgeklügelt ist das der Dekodierer ~weiß~ wann der zu dekodierende Stream zu ende ist. Man kann sich also einfach den DeCss Source nehmen den kodieren und einfach hinten solange Bytes anfügen bis die Bytefolge einer Primzahl entspricht ohne das spätere Dekodierergebnis zu ändern.

Ralf Jansen hat folgendes geschrieben :

Zitat: Merkwürdich ist doch aber, das ausgerechnet eine Primzahl -mit gzip dekodiert- den Quelltext von DeCSS ergibt. Ich glaube du interpretierst da zuviel rein. Ich vermute das der Alghorithmus von zip so ausgeklügelt ist das der Dekodierer ~weiß~ wann der zu dekodierende Stream zu ende ist. Man kann sich also einfach den DeCss Source nehmen den kodieren und einfach hinten solange Bytes anfügen bis die Bytefolge einer Primzahl entspricht ohne das spätere Dekodierergebnis zu ändern.

Genau! Außerdem scheints wirklich nur mit gzip zu funktioneren, denn das hört nach zwei #0 bytes auf. 7Z und Rar sind nicht so einfach zu überlisten. Und es dauert auch nicht lange, so eine Primzahl zu berechen. Beispiel: der Text aus dem 1. Beitrag "Hallo, ... gzip zu tun?". Er wird ge-gzipt, hex ausgelesen, zwei #0 Bytes angehängt, als MP-Integer interpretiert und einfach die nächste Primzahl gesucht:



Allerdings benutzt meine Bibliothek den BPSW-Primtest, also wird die eigentliche Zeit für eine hieb-und-stichfeste Verifikation der Primeigenschaft wahrscheinlich wesentlich länger sein als bis 10 sec für die Berechnung.

Gammatester


Edit: Die Zahl ist wirklich prim (eigentlich Schade, sonst wär's das erste Gegenbeispiel für BPSW). Zeitbedarf mit Primo 3.0.7: Initialization=0.25s, 1stPhase=5mn 50s, 2ndPhase=43.34s, Total=6mn 34s)

FinnO hat folgendes geschrieben :

na, dass das Zufall ist, ist irgendwie selbstverständlich. Schließlich hat jede Zahl ein Bitmuster, nicht nur Primzahlen.

Letztendlich kann man auch an jeder (natürlichen) Zahl irgendwelche Eigenschaften finden, ja dieser fast schon andichten, die sie originell, einzigartig, unverwechselbar macht. Mathematiker sind diesbezüglich grenzenlos hartnäckig und kreativ spürsinnig. Und unter diesem Aspekt der nachweislichen Einzigartigkeit oder bestenfalls einer Gruppierung weniger Zahlen mit ähnlichen bzw. gemeinsamen Eigenschaften (siehe Primzahlen) kann man eben jede Zahl veröffentlichen, wenn man es nur gut und/oder genug begründen kann. Ansonsten ist die bloße Veröffentlichung einer Zahl auch ohne einen solchen Hinweis rechtlich einwandfrei, wenn man ihre "dunkle" Seite ebenfalls verschweigt, dann ist ja keine unlautere Absicht nachzuweisen. (Natürliche) Zahlen als Abstraktion der Anzahlen (von Mengen) natürlicher Objektes als solche existieren nun einmal objektiv und unabhängig vom menschlichen Geiste (sonst hätten Sie keine von den Gehirnen unabhängige Eigenschaften) und lassen sich nicht einmal von US-amerikanischen Gesetzen bzw. Gerichten, die sogar schon die Mondoberfläche sich "angeeignet" haben sollen, verbieten. Zählt man sie einfach der Reihe nach durch, gelangt man mit hunderprozentiger Sicherheit irgendwann in die Illegalität, in die Kriminalität.

Allein das Syntagma "illegale Primzahl" zeigt doch den ganzen Widersinn, die Lächerlichkeit, die Hirnrissigkeit gerade des US-amerikanischen (Un-)Rechtssystems auf. Ich nehme es jedenfalls nicht ernst.

Bei diesen "illegalen Primzahlen" geht es ja um den Sinn einer Veröffentlichung von illegalen Daten auf eine legale weise. Daher sucht man sich am einfachsten Primzahlen, da diesen in der Mathematik am meisten Beachtung geschenkt wird und auch bestimmte Primzahlen, ob nun aufgrund ihrer Art, Bildungsvorschrift oder Länge, veröffentlicht werden. Berichtet man anschließend über die weitere Besunderheit dieser Zahl, können alle Personen auf diese illegalen Daten zugreifen.

Ähnliches wurde ja auch mit dem Quellcode von PGP gemacht, dessen Export aus den USA illegal gewesen wäre. Daher wurde dieser als Buch in maschinenlesbarer Schrift samt Prüfsummen veröffentlicht und anschließend exportiert, da diese keine Exportbeschränkungen haben.

Diesen Gedanken kann man sogar noch weitertreiben und verallgemeinern: Jedes urheberrechtlich geschützt Werk, sei es Audio, Video, Photo, Gemälde, Plastik, etwas Schriftliches (z.B. Buch), ein Algorithmus, eine Erfindung oder Entdeckung läßt sich digitalisieren und damit letzlich einer - in der Regel immens großen - Zahl zuordnen (wobei diese Zuordnung natürlich vom Digitalisierungsverfahren abhängt und damit nicht eineindeutig ist). Wenn das mit der Verjustifizierung des Bereiches/Raumes der natürlichen Zahlen so weitergeht, dann gehen den Mathematikern allmählich die (großen) Zahlen aus, vielleicht wird sogar die Mathematik als ganzes abgeschafft werden müssen.