Diskussion:Illegale Primzahl

Umwandlung der Primzahl

Im ersten Absatz steht, dass man die Primzahl in ihrer binären Darstellung mit Gzip dekomprimiert. Aber müsste es nicht eigentlich ihre hexadezimale Darstellung sein? 172.208.156.11 17:09, 20. Aug 2006 (CEST)

Laut http://www.heise.de/newsticker/meldung/16226 ist dem so. --84.153.150.153 00:50, 7. Sep 2006 (CEST)

Heise irrt, denn gzip sagt:

  gzip: illegaleprimzahlinhexadezimal: not in gzip format

und illegaleprimzahlinhexadezimal beginnt mit '1f8b', was nach [RFC 1952] die ersten zwei bytes einer gzip-datei in Hexadezimaldarstellung sind. Offensichtlich muss man also die Binärdarstellung mit 8 bit pro Byte, nicht die Hexadezimaldarstellung mit 4 bit pro Zeichen an gzip füttern. Es wäre ja auch komisch, wenn eine komprimierte, also entropiereduzierte Datei noch 4 bit pro Byte verschenken würde. ╞►B²◄╬►【ぢすくすょん】◄╡ 15:27, 2. Mär. 2008 (CET)

Also binär bedeutet, als Einsen und Nullen und wenn man je 4 zusammenfasst kommt man zu einer hexadezimalen Darstellung, wobei die Darstellung keinen Einfluss auf die Zahl hat. Auch nicht, ob sie Primzahl ist oder nicht, sondern lediglich, wie wir diese Zahl interpretieren/lesen. Es ist also folglich egal, ob man die Zahl als hexadezimal- oder binär- Zahl ausdruckt. Natürlich kann man aber nicht einfach einen beliebigen Editor nehmen und diese Zahl als binär oder hex-Zahl reinschreiben und dann abspeichern, da Editoren standartmäßig nicht als Hex-Code oder Binär-Code abspeichern, selbst wenn nur 1 und 0 bzw. 1 bis F drinstehen. Das einfachste wird ein Hex-Editor sein, einen Binäreditor kenn ich nicht, aber es sollte einfach sein sich sowas einfach zu progammieren. --93.133.22.55 23:40, 20. Mär. 2009 (CET)

Unendlichkeit der illegalen Primzahl

Im ersten Absatz steht, dass die Unendlichkeit der illegalen Primzahlen mit dem dirichletschen Primzahlsatz bewiesen werden könne. Nach einer Suche im Netz (z.B. dieser link) habe ich allerdings keinen Beweis auf Basis dieses Satzes gefunden und eine triviale Anwendung scheint (auch nach Diskussion mit kompetentem Kumpel, diplomierter Physiker) nicht möglich.

Allerdings habe ich mit Hilfe des Primzahlsatzes einen Beweis gefunden, dass die Menge der illegalen Primzahlen tatsächlich unendlich ist:

Sei $a$ die Zahl, die dem gepackten Code mit Nullterminierung entspricht. Offenbar ist jede Primzahl $p=a\cdot 256^{k}+b$ mit $b,k\in \mathbb {N}$ und $256^{k}>b$ eine illegale Primzahl.

Nach dem Primzahlsatz ist die Anzahl der Primzahlen zwischen $a\cdot 256^{k}$ und $a\cdot 256^{k}+256^{k}=(a+1)\cdot 256^{k}$ mindestens

$n_{k}:={\frac {(a+1)\cdot 256^{k}}{\ln((a+1)\cdot 256^{k})}}(1-\epsilon _{k})-{\frac {a\cdot 256^{k}}{\ln(a\cdot 256^{k})}}(1+\epsilon _{k})$

wobei $\epsilon _{k}\in \mathbb {R} _{\geq 0}$ und $\lim \limits _{k\rightarrow \infty }\epsilon _{k}=0$.

Die folgenden Rechnungen ergeben eine Abschätzung für $n_{k}$:

$n_{k}=256^{k}\cdot ({\frac {(a+1)(1-\epsilon _{k})}{k\cdot \ln(256)+\ln(a+1)}}-{\frac {a(1+\epsilon _{k})}{k\cdot \ln(256)+\ln(a)}})$

Es sei $\delta _{k}$ definiert durch:

$k\cdot \ln(256)+\ln(a+1)=(k\cdot \ln(256)+\ln(a))(1+\delta _{k})\Rightarrow$ $k\cdot \ln(256)+\ln(a)+\ln(1+{\frac {1}{a}})=(k\cdot \ln(256)+\ln(a))(1+\delta _{k})\Rightarrow$ $\delta _{k}:={\frac {\ln(1+{\frac {1}{a}})}{k\cdot \ln(256)+\ln(a)}}\Rightarrow \lim \limits _{k\rightarrow \infty }\delta _{k}=0$

Also:

$n_{k}=256^{k}\cdot ({\frac {(a+1)(1-\epsilon _{k})}{(k\cdot \ln(256)+\ln(a))\cdot (1+\delta _{k})}}-{\frac {a(1+\epsilon _{k})}{k\cdot \ln(256)+\ln(a)}})=$ ${\frac {256^{k}}{k\cdot \ln(256)+\ln(a)}}\cdot ({\frac {(a+1)(1-\epsilon _{k})}{1+\delta _{k}}}-a(1+\epsilon _{k}))=$ ${\frac {256^{k}}{(1+\delta _{k})(k\cdot \ln(256)+\ln(a))}}\cdot ((a+1)(1-\epsilon _{k})-a(1+\delta _{k})(1+\epsilon _{k}))=$ ${\frac {256^{k}}{(1+\delta _{k})(k\cdot \ln(256)+\ln(a))}}\cdot (1-(\epsilon _{k}+2a\epsilon _{k}+a\delta _{k}+a\delta _{k}\epsilon _{k}))$

Da $\epsilon _{k},\delta _{k}\rightarrow ^{k\rightarrow \infty }0$ gilt weiter:

$\exists K'\in \mathbb {N} :\forall k>K':\epsilon _{k}+2a\epsilon _{k}+a\delta _{k}+a\delta _{k}\epsilon _{k}<{\frac {1}{2}}\wedge \delta _{k}<1$

daraus folgt:

$\exists K\in \mathbb {N} :\forall k>K:n_{k}>{\frac {256^{k}}{(1+\delta _{k})(k\cdot \ln(256)+\ln(a))}}\cdot {\frac {1}{2}}>$${\frac {256^{k}}{2(k\cdot \ln(256)+\ln(a))\cdot 2}}>1$

Zusammenfassend gibt es also eine natürliche Zahl K, so dass in dem Intervall zwischen $a\cdot 256^{k}$ und $(a+1)\cdot 256^{k}$ wenigstens eine illegale Primzahl liegt, falls nur $k>K$ ist.

Anders ausgedrückt: Hat $a$ in hexadezimaler Darstellung $l$ Stellen, so gibt es gibt es eine untere Schranke $K$, so dass es wenigstens eine illegale Primzahl mit $l+2k$ hexadezimalen Stellen hat, für beliebiges $k>K$. (Die 2 in $l+2k$ kommt daher, dass eine Hexadezimalstelle genau 4 Bit zur Darstellung braucht und ein Byte 8 bit hat, also genau doppelt so viele.)

Daraus folgt natürlich, dass es unendlich viele illegale Primzahlen gibt. Durch Angabe von konstruktiven Schranken für $\epsilon _{k},\delta _{k}$ (was möglich ist) kann die Schranke $K$ sogar explizit angegeben werden.

Das ist ja schön für dich, aber Was_Wikipedia_nicht_ist sagt im Absatz 2 ganz klar, dass das hier nicht hingehöhrt.

Unter Theoriebildung verstehe ich was anderes als eine leichte Übungsaufgabe, die - abgesehen vom Primzahlsatz - doch bitte mindestens jeder Abiturient nachvollziehen können sollte. Wollte den Beweis nur der Vollständigkeit halber dazunehmen. Außerdem heißt es eben in dem erwähnten Punkt 2, dass nicht nachprüfbare Aussagen unerwünscht sind, was eher dafür spricht, dass der Beweis dazu gehört.

Wie auch immer, es bleiben Fragen und ein paar Antworten:

1. Gibt es beweisbar unendlich viele illegale Primzahlen? Antwort: Ja, der Primzahlsatz liefert einen Beweis.

2. Kann dieser Beweis auch mit dem Dirichletschen Primzahlsatz erbracht werden, wie im Text behauptet? Antwort: imho offen.

3. Gibt es konstruktive Schranken nach unten für die Anzahl illegaler Primzahlen von gegebener Länge? Antwort: Ja, obiger Beweis liefert sie.

Sinn?

Mir wird als Leser des Artikels nicht klar, wieso es zum gegebenen Thema überhaupt relevant ist, ob die Zahl eine Primzahl ist oder nicht. Der relevante Punkt ist doch: Alle digitalen Dokumente sind im Grunde nichts anderes als Zahlen mit vielen Stellen. Wenn es digitale Dokumente gibt, die "illegal" sind, dann bedeutet das folglich, dass damit die betreffenden Zahlen für "illegal" erklärt werden. Was eine absurde Sache ist. Und für die Absurdität der Sache ist es doch egal, ob es eine durch 2 teilbare Zahl ist oder eine Primzahl. Habe ich irgend etwas übersehen? --Neitram ✉ 15:28, 8. Sep. 2016 (CEST)

Primzahlen sind "intrinsisch archivierungswürdig". Mathematiker haben ein Interesse daran, Aufzeichnungen darüber zu führen, welche Zahlen eine Primzahl sind. --Echoray (Diskussion) 18:54, 8. Sep. 2016 (CEST)

Das verstehe ich, Primzahlen sind Lieblingszahlen der Mathematiker. Aber ansonsten habe ich schon Recht, dass etwa die Illegalität der Zahl 100000000002 doch die gleiche Absurdität ist wie die Illegalität der Zahl 100000000003? --Neitram ✉ 09:21, 9. Sep. 2016 (CEST)

In der englischen Wikipedia haben sie das auch erkannt und es gibt dort zwei Artikel: en:Illegal prime und en:Illegal number. --Echoray (Diskussion) 12:27, 9. Sep. 2016 (CEST)

Ah, danke! Dann notiere ich mir mal Illegale Zahl auf meinen Wunschzettel. --Neitram ✉ 13:27, 9. Sep. 2016 (CEST)

Ich habe jetzt Illegale Zahl angelegt. --Neitram ✉ 14:55, 12. Jun. 2018 (CEST)