2 Integerwerte in einem Integerwert reversibel speichern?

[3_of_8]

Außerdem "verschwendet" man dann recht viel Speicherplatz und man erhält die Zahlen nicht mehr in konstanter Zeit (O(1)), sondern in O(sqrt(pq)).

[negaH]

Zitat:

Nein. Er meinte, das die 12. und die 20. Primzahl miteinander multipliziert werden. Dann ist es selbstverständlich eindeutig (natürlich nicht bezüglich p*q=q*p). Allerdings werden die Zahlen sehr schnell sehr groß.

Ok, macht aber noch weniger Sinn. Es gibt weniger Primzahlen als Nichtprimzahlen, logisch. Das bedeutet gäbe es unendlich viele Nichtprimzahlen dann benötigen wir mehr als unendlich viele Primzahlen. Soweit die methematrische Unmöglichkeit des Vorschlages.

Technisch gesehen betrachten wir ja nur Zahlen im Bereich von Integer etc.pp. Dann entsteht aber das problem diese beiden Zahlen wieder zu extrahieren, das ist eine sehr aufwendige Operation. Hat aber Manuel im vorherigen Posting korrekt erklärt.

Es gibt Zahlensysteme die modulare Merhfachringe zu den kleinen Primzahlen benutzen, siehe D.J.Bernstein. Deren "Packungsdichte" entspricht den natürlichen Zahlen und man kann jede Ganzzahl damit eineindeutig darstellen. Allerdings benutzt man solche Ringe nur deswegen um sehr große Ganzzahlen > 1024 Bit in ein Zahlensystem zu überführen -> modulare multiple Ringe zu Primzahlen, um alle Berechnungen mit solchen großen Zahlen zb. auf 32 Bit Ebene durchführen zu können. Man benutzt also das Zahlendarstelung zb. alle Reste der modularen Division der kodierten Zahl zu den kleinen Primzahlen bis < 2^32. Die maximal so kodierbare Zahl wäre dann exakt so groß wie das Primzahlprodukt aller Primzahlen < 2^32 -1. Der benötigte Speicherverbrauch wäre dann die Anzahl aller Primzahlen kleiner 2^32 -> P(2^32-1) * 4 Bytes. Jede mathematische Operation wie Addition/Subtraktion usw. würde nun dieses Array[] von Modularen Resten zu Primzahlen addieren per 32 Bit Operationen und somit entsteht kein Überlauf/Unterlauf mehr innerhalb dieser Ringe. Die Umrechnung dieser Zahlendarstellung wieder zurück in natürliche Zahlen erfolgt mit Garner's Version des Chinisischem Restsatzes.

Gruß Hagen

[Der_Unwissende]

Zitat:

Zitat von negaH

Ok, macht aber noch weniger Sinn. Es gibt weniger Primzahlen als Nichtprimzahlen, logisch. Das bedeutet gäbe es unendlich viele Nichtprimzahlen dann benötigen wir mehr als unendlich viele Primzahlen. Soweit die methematrische Unmöglichkeit des Vorschlages.

[OT]
Wie zeigt man das denn? Also ich denke mal wir reden über Natürliche Zahlen (oder Ganze, da Integer-Datentyp). Natürlich gibt es dort jeweils abzählbar-viele Zahlen, die keine Primzahl sind. Aber wurde gezeigt, dass es nur endlich viele Primzahlen gibt? Ich meine man kann auch ganze Zahlen abzählen, was ja auch heißt, dass die Menge der ganzen und der natürlichen Zahlen gleich mächtig ist.

Wie gesagt OT, würde mich nur interessieren, falls also jmd. weiß dass das bewiesen wurde wäre ein Hinweis auf den entsprechenden Beweis oder dessen Idee sehr nett, danke!
[/OT]

Gruß Der Unwissende

[Klaus01]

Zitat:

Zitat von Der_Unwissende

Zitat:

Zitat von negaH

Ok, macht aber noch weniger Sinn. Es gibt weniger Primzahlen als Nichtprimzahlen, logisch. Das bedeutet gäbe es unendlich viele Nichtprimzahlen dann benötigen wir mehr als unendlich viele Primzahlen. Soweit die methematrische Unmöglichkeit des Vorschlages.

[OT]
Wie zeigt man das denn? Also ich denke mal wir reden über Natürliche Zahlen (oder Ganze, da Integer-Datentyp). Natürlich gibt es dort jeweils abzählbar-viele Zahlen, die keine Primzahl sind. Aber wurde gezeigt, dass es nur endlich viele Primzahlen gibt? Ich meine man kann auch ganze Zahlen abzählen, was ja auch heißt, dass die Menge der ganzen und der natürlichen Zahlen gleich mächtig ist.

Wie gesagt OT, würde mich nur interessieren, falls also jmd. weiß dass das bewiesen wurde wäre ein Hinweis auf den entsprechenden Beweis oder dessen Idee sehr nett, danke!
[/OT]

Gruß Der Unwissende

Ist es nicht so, das es unendlich viele Primzahlen und unendlich viele Ganzzahlen gibt.
Und mehr als unendlich geht nicht.
Es sollte dann also auch möglich sein jeder Ganzzahl eine Primzahl zuzuordnen.
Wie groß die Primzahlen dann sein müssen steht dann auf einem anderen Blatt.

Hoffe nicht ganz falsch zu liegen.

Grüße
Klaus

[Der_Unwissende]

Zitat:

Zitat von Klaus01

Ist es nicht so, das es unendlich viele Primzahlen und unendlich viele Ganzzahlen gibt.

Mir ist eben auch so, deswegen würde mich eben der Gegenbeweis interessieren (könnte auch die Sicherheit der Verschlüsselungen, die auf Primzahlen aufbauen ziemlich senken, da man nur die endlich vielen Primzahlen berechnen muss - was lange genug dauert - und ziemlich effizient all diese Verschlüsselungen knacken kann).

[jfheins]

Es gibt unendlich viele Primzahlen - aber in einem Zahlenraum von MinInt..MaxInt gibt es bedeutend mehr nicht-Primzahlen, weshalb man Probleme hätte, die 2.000.000.000-te Primzahl in einen Integer zu bekommen ;)

Beweis, Kurzversion:

Angenommen, es gibt endlich viele Primzahlen.

:arrow: Multipliziere alle bekannten Primzahlen miteinander und addiere 1
Entweder:
:arrow: Ergebnis ist eine Primzahl :arrow: Annahme wiederlegt
oder:
:arrow: Das Ergebnis ist keine Primzahl - Primfaktorzerlegung ergibt eine Primzahl, die größer als alle anderen ist (Da ja alle Primzahlen multipliziert wurden und noch 1 addiert wurde) :arrow: Annahme widerlegt

;)

[3_of_8]

Natürlich kann man jeder ganzen Zahl eine Primzahl bijektiv zuordnen.

Das könnte man zum Beispiel so machen:
f: Z x N
f(x)=p(1) für x=0
f(x)=p(2x) für x>0
f(x)=p(-2x+1) für x<0

p: N x N
p(x)=Die x. Primzahl


Wie man sieht, ist damit jeder ganzen Zahl eine Primzahl bijektiv zugeordnet. Möglich ist das, wie bereits angesprochen, weil |N|=|Z|=aleph.

Sobald man allerdings nicht mehr mit Z und N arbeitet, sondern mit Teilmengen von diesen (wie es bei Computern nun mal der Fall ist) ist diese Zuordnung natürlich nicht mehr ganz möglich, da die Größe der Primzahlen schneller nach unendlich strebt als die der Zahlen, die man mit ihnen verknüpft. Ich habe vor kurzem mal ein paar Millionen Primzahlen berechnen lassen, und ich weiß es jetzt nicht mehr genau, aber ich glaube, dass man mit den Primzahlen im Cardinal-Bereich nur Zahlen von ~-100 Mio. bis +100 Mio. darstellen könnte. (nach obiger Methode)

[Apollonius]

Zitat:

Es gibt unendlich viele Primzahlen - aber in einem Zahlenraum von MinInt..MaxInt gibt es bedeutend mehr nicht-Primzahlen, weshalb man Probleme hätte, die 2.000.000.000-te Primzahl in einen Integer zu bekommen

Man sollte auch noch den Teil nach dem aber beweisen, also: im Zahlenraum 0..n gibt es mindestens genausoviele nicht-Primzahlen wie Primzahlen.
Für n<3 ist der Fall klar; bei n>=3 gibt es genau eine gerade Primzahl und mindestens eine ungerade nicht-Primzahl (1).
Die Behauptung folgt direkt.

[Der_Unwissende]

Zitat:

Zitat von jfheins

Es gibt unendlich viele Primzahlen - aber in einem Zahlenraum von MinInt..MaxInt gibt es bedeutend mehr nicht-Primzahlen, weshalb man Probleme hätte, die 2.000.000.000-te Primzahl in einen Integer zu bekommen ;)

Das ist klar, bezog mich auch nur auf

Zitat:

Zitat von negaH

Es gibt weniger Primzahlen als Nichtprimzahlen, logisch. Das bedeutet gäbe es unendlich viele Nichtprimzahlen dann benötigen wir mehr als unendlich viele Primzahlen. Soweit die methematrische Unmöglichkeit des Vorschlages

Soweit ich mich nicht irre ist eben die Implikation, dass es mehr als unendliche vieler Primzahlen bedarf um alle Nichtprimzahlen zu kodieren würde ich eben als falsch ansehen. Und wenn es eine Bijektion zwischen einer abzählbaren Menge und eben der Menge aller Primzahlen gibt, dann sind diese Mengen gleich mächtig und die mathematische Möglichkeit des Vorschlags bleibt gewahrt (wenn auch der Ansatz nicht unbedingt sehr effizient ist). Dem Threadsteller geht es aber eben auch nur um die theoretische Möglichkeit und für einen unendlichen Zahlenraum denke ich, dürfte dies eine eindeutige Möglichkeit sein, zwei Zahlen zu kodieren un diese wieder zu dekodieren.

[negaH]

Hm warum sollte das falsch sein ?

Es gibt in einem begrenzten Zahlenbereich immer mehr zusammengesetzte Zahlen als Primzahlen. (mal abgeshen vom Bereich 2 bis 5 oä.).
Das bedeutet das wenn man die Zahlen in diesem Beeich per Primzahlen kodieren wollte so reichen die Primzahlen innerhalb dieses Breiches dafür nicht aus.

Nun definieren wir diesen Bereich als unendlich groß, also benötigen wir mehr als unendlich viele Primzahlen. Es stimmt schon, unendlich bedeutet unendlich. Das heist aber nicht das wenn man die Menge von Zahlen betrachtet im Verhältnis zu einer unendlichen Menge von Zahlen wir denoch mehr als unendlich viele Primzahlen benötigen. Wir definieren also die Menge A aller Zahlen und versuchen diese Zahlen in die Menge B von Primzahlen zu mappen. Wenn Menge A eine Kardinalität von unendlich besitzt so muß Menge B ebenfalls unendlich sein, dann existiert aber denoch keine Schnittmenge C aus A und B die gleich groß unendlich wäre. Da dann die Menge der Primzahlen B in der Menge aller Zahlen A vollständig aufgeht. Menge A die unendlich groß wäre ist denoch größer als Menge B die ebenfalls unendlich groß wäre und Menge B ist nur eine Teilmenge von A. Wir wollen aber alle Zahlen der Menge A kodieren und dazu reicht die Anzahl der Primzahlen (Menge B) die in Menge A enthalten sind nicht aus. Also selbst wenn Menge A unendlich groß wäre so benötigten wir eine Menge B von primzahlen mit gleicher Größe wie Menge A.

Hm, schwer zu erklären ;)

Nochmal

Menge A, alle ganzen Zahlen inklusive Primzahlen
Menge C, alle Primzahlen aus Menge A
Menge B, nur Primzahlen

Menge A und B müssen gleiche Kardinalität besitzen, also exakt gleiche Anzahl von Zahlen
Menge C wird immer weitaus kleiner sein als Menge A, logisch gibt es doch weniger Primzahlen als zusammengesetzte Zahlen

Ergo die Menge C wird immer kleiner Menge B sein.
Wenn Menge A unendlich groß ist dann wird Menge C auch unendlich groß sein aber denoch kleiner als Menge A
Wenn Menge B exakt gleich groß Menge A sein muß aber Menge C immer kleiner als Menge A ist dann heist dies,

das größte Element=Zahl aus Menge A ist Zahl unendlich und das größte Element in Menge C ist größer unendlich.

Wir rechnen eben nicht mehr mit Zahlen sondern mit Mengen deren Elemente Zahlen sind.

Jetzt ist die Frage, gibt es eine Zahl die großer ist als unendlich groß ?
Und gibt es eine Menge A die unendlich viele Zahlen enthält die aber denoch kleiner sein kann als eine andere Menge B mit unendlich vielen Zahlen.


Gruß Hagen